#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int n, N, mod;
vector<vector<pair<int, int>>> segs;
vector<vector<int>> add;
SegTree() {}
SegTree(int _n, int _mod) {
n = _n, mod = _mod;
N = 1;
while (N < n) {
N <<= 1;
}
segs.resize(2 * N);
add.resize(2 * N);
}
void build(int v, int tl, int tr, const vector<int>& a) {
if (tl + 1 == tr) {
if (tl < n) {
segs[v] = {{0, a[tl] - 1}, {a[tl], mod - 1}};
add[v] = {a[tl] + 1 < mod ? a[tl] + 1 : 0, a[tl]};
} else {
segs[v] = {{0, mod - 1}};
add[v] = {0};
}
return;
}
int m = tl + (tr - tl) / 2;
build(2 * v, tl, m, a);
build(2 * v + 1, m, tr, a);
for (int i = 0; i < (int)segs[2 * v].size(); ++i) {
int l = segs[2 * v][i].first, r = segs[2 * v][i].second;
int nxt = l + add[2 * v][i];
if (nxt >= mod) { nxt -= mod; }
int j = upper_bound(segs[2 * v + 1].begin(), segs[2 * v + 1].end(), make_pair(nxt, mod)) - segs[2 * v + 1].begin() - 1;
while (segs[2 * v + 1][j].second - nxt < r - l) {
segs[v].emplace_back(l, l + segs[2 * v + 1][j].second - nxt);
add[v].emplace_back(add[2 * v][i] + add[2 * v + 1][j]);
if (add[v].back() >= mod) {
add[v].back() -= mod;
}
l = segs[v].back().second + 1;
nxt = l + add[2 * v][i];
if (nxt >= mod) { nxt -= mod; }
++j;
if (j == (int)segs[2 * v + 1].size()) {
j = 0;
}
assert(segs[2 * v + 1][j].first <= nxt && segs[2 * v + 1][j].second >= nxt);
}
segs[v].emplace_back(l, r);
add[v].emplace_back(add[2 * v][i] + add[2 * v + 1][j]);
if (add[v].back() >= mod) {
add[v].back() -= mod;
}
}
}
void build(const vector<int>& a) {
build(1, 0, N, a);
}
int query(int v, int tl, int tr, int l, int r, int rocks) {
if (l <= tl && tr <= r) {
int pos = upper_bound(segs[v].begin(), segs[v].end(), make_pair(rocks, mod)) - segs[v].begin() - 1;
rocks += add[v][pos];
if (rocks >= mod) { rocks -= mod; }
return rocks;
}
int m = tl + (tr - tl) / 2;
if (l < m) {
rocks = query(2 * v, tl, m, l, r, rocks);
}
if (m < r) {
rocks = query(2 * v + 1, m, tr, l, r, rocks);
}
return rocks;
}
int query(int l, int r, int rocks) {
if (l >= r) { return rocks; }
return query(1, 0, N, l, r, rocks);
}
~SegTree() {}
};
const int maxlog = 17, maxn = 12e4 + 1;
long long prefLeq[maxn][maxlog], prefReq[maxn][maxlog], pref[maxn];
int cntReq[maxn][maxlog], Log[maxn];
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<int> posBPref, posRSuf;
for (int i = 0; i < n; ++i) {
if (s[i] == 'B') {
posBPref.emplace_back(i);
} else {
posRSuf.emplace_back(i);
}
}
reverse(posRSuf.begin(), posRSuf.end());
posBPref.emplace_back(n);
posRSuf.emplace_back(-1);
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
pref[i + 1] = pref[i] + a[i];
for (int k = 0; k < maxlog; ++k) {
prefLeq[i + 1][k] = prefLeq[i][k] + (a[i] <= (1 << k)) * a[i];
prefReq[i + 1][k] = prefReq[i][k] + (a[i] > (n - (1 << k))) * a[i];
cntReq[i + 1][k] = cntReq[i][k] + (a[i] > (n - (1 << k)));
}
}
SegTree st(m, n + 1);
st.build(a);
auto makeStep = [&](int j, int& prefR, int& sufB, int& addPref, int& addSuf) -> void {
int cntB = (int)posBPref.size() - 1 - addPref + addSuf;
char type;
if (j <= prefR) {
type = 'R';
} else if (j > n - sufB) {
type = 'B';
} else {
type = s[j - 1];
}
if (type == 'B') {
++j;
}
if (cntB >= j) {
// take j-th B
addPref += j;
} else {
// take n + 1 - j -th R
addSuf += n + 1 - j;
}
if (addPref >= (int)posBPref.size() || addSuf >= (int)posRSuf.size() || (posBPref[addPref] + n - posRSuf[addSuf] - 1 > n)) {
if (cntB >= j) {
// addPref -= j;
int leftB = cntB - sufB;
sufB -= (j - leftB);
prefR = n - sufB;
} else {
// addSuf -= (n + 1 - j);
int cntR = n - cntB;
int rightR = cntR - prefR;
prefR -= (n + 1 - j - rightR);
sufB = n - prefR;
}
addPref = (int)posBPref.size() - 1, addSuf = (int)posRSuf.size() - 1;
} else {
prefR = posBPref[addPref], sufB = n - posRSuf[addSuf] - 1;
}
// cerr << "cntB: " << cntB << ", type: " << type << ", addPref: " << addPref << ", addSuf: " << addSuf << '\n';
assert(prefR + sufB <= n);
};
auto collided = [&](int addPref, int addSuf) -> bool {
addPref = min(addPref, (int)posBPref.size() - 1);
addSuf = min(addSuf, (int)posRSuf.size() - 1);
// cerr << "Rs: " << posBPref[addPref] << ", Bs: " << n - posRSuf[addSuf] - 1 << '\n';
return posBPref[addPref] + n - posRSuf[addSuf] - 1 >= n;
};
auto willCollide = [&](int prefR, int sufB, int addPref, int addSuf, int l, int r) -> bool {
int lgr = Log[prefR], lgb = Log[sufB];
long long newAddPref = (lgr != -1 ? addPref + prefLeq[r][lgr] - prefLeq[l][lgr] : addPref);
long long newAddSuf = (lgb != -1 ? addSuf + n * 1ll * (cntReq[r][lgb] - cntReq[l][lgb]) - (prefReq[r][lgb] - prefReq[l][lgb]) : addSuf);
if (newAddPref >= (int)posBPref.size() || newAddSuf >= (int)posRSuf.size()) {
return true;
}
return collided(newAddPref, newAddSuf);
};
auto completeTillCollide = [&](int& prefR, int& sufB, int& addPref, int& addSuf, int l, int r) -> int {
// collision is on [l, r) ?
int lgr = Log[prefR], lgb = Log[sufB];
int left = l, right = r + 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (willCollide(prefR, sufB, addPref, addSuf, l, mid)) {
right = mid;
} else {
left = mid;
}
}
// cerr << "left: " << left << '\n';
if (lgr != -1) {
addPref += prefLeq[left][lgr] - prefLeq[l][lgr];
}
if (lgb != -1) {
addSuf += n * 1ll * (cntReq[left][lgb] - cntReq[l][lgb]) - (prefReq[left][lgb] - prefReq[l][lgb]);
}
prefR = posBPref[addPref], sufB = n - posRSuf[addSuf] - 1;
// cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
if (left < r) {
// collided
makeStep(a[left], prefR, sufB, addPref, addSuf);
return left + 1;
}
return left;
};
auto hasBad = [&](int prefR, int sufB, int l, int r) -> bool {
int lgr = Log[prefR], lgb = Log[sufB];
long long goodSum = 0;
if (lgr != -1) {
goodSum += prefLeq[r][lgr] - prefLeq[l][lgr];
}
if (lgb != -1) {
goodSum += prefReq[r][lgb] - prefReq[l][lgb];
}
return goodSum < pref[r] - pref[l];
};
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l;
int prefR = posBPref[0], sufB = n - posRSuf[0] - 1;
int addPref = 0, addSuf = 0;
if (prefR == 0 && sufB == 0) {
makeStep(a[l], prefR, sufB, addPref, addSuf);
++l;
}
while (!collided(addPref, addSuf) && l < r) {
// cerr << "!\n";
int left = l, right = r + 1;
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (hasBad(prefR, sufB, l, mid)) {
right = mid;
} else {
left = mid;
}
}
// left is first bad
l = completeTillCollide(prefR, sufB, addPref, addSuf, l, left);
if (!collided(addPref, addSuf) && l < r) {
makeStep(a[l], prefR, sufB, addPref, addSuf);
++l;
}
}
int ans;
// cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
if (collided(addPref, addSuf)) {
ans = st.query(l, r, prefR);
} else {
// cerr << "prefR: " << prefR << ", sufB: " << sufB << ", addPref: " << addPref << ", addSuf: " << addSuf << ", l: " << l << ", r: " << r << '\n';
ans = (int)posRSuf.size() - 1 + addPref - addSuf;
// ans = cntRocks[n - sufB] - cntRocks[prefR] + prefR;
}
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Log[0] = -1, Log[1] = 0;
for (int i = 2; i < maxn; ++i) {
Log[i] = Log[i >> 1] + 1;
}
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
