#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back
const int BIG = 1e9 + 10;
#define int ll
struct segTreeSum
{
vector<pii> tree;
int sz;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz, {0, -1});
}
void upd(int v, int lv, int rv, int val)
{
tree[v].f = (rv - lv) * val;
tree[v].s = val;
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1 or tree[v].s == -1)
return;
int m = (lv + rv) >> 1;
upd(v * 2 + 1, lv, m, tree[v].s);
upd(v * 2 + 2, m, rv, tree[v].s);
tree[v].s = -1;
}
void set(int l, int r, int val, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, lv, rv, val);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
set(l, r, val, v * 2 + 1, lv, m);
set(l, r, val, v * 2 + 2, m, rv);
tree[v].f = tree[v * 2 + 1].f + tree[v * 2 + 2].f;
}
void set(int l, int r, int val)
{
set(l, r, val, 0, 0, sz);
}
int get(int l, int r, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
return tree[v].f;
if (r <= lv or rv <= l)
return 0;
int m = (lv + rv) >> 1;
return get(l, r, v * 2 + 1, lv, m) + get(l, r, v * 2 + 2, m, rv);
}
int get(int l, int r)
{
return get(l, r, 0, 0, sz);
}
int getKthFromStart(int k, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
{
assert(k == 0);
return lv;
}
int m = (lv + rv) >> 1;
if (tree[v * 2 + 1].f <= k)
return getKthFromStart(k - tree[v * 2 + 1].f, v * 2 + 2, m, rv);
return getKthFromStart(k, v * 2 + 1, lv, m);
}
int getKthFromStart(int k)
{
return getKthFromStart(k, 0, 0, sz);
}
int getKthFromEnd(int k, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
{
assert(k == 0);
return lv;
}
int m = (lv + rv) >> 1;
if (tree[v * 2 + 2].f <= k)
{
return getKthFromEnd(k - tree[v * 2 + 2].f, v * 2 + 1, lv, m);
}
return getKthFromEnd(k, v * 2 + 2, m, rv);
}
int getKthFromEnd(int k)
{
return getKthFromEnd(k, 0, 0, sz);
}
};
// struct mySegTree
// {
// struct Node
// {
// int mn = BIG, mx = -1, op = 0;
// };
// vector<Node> tree;
// int sz = 1;
// int mod;
// void init(int n)
// {
// mod = n + 1;
// while (sz < n)
// sz *= 2;
// tree.resize(2 * sz, {BIG, -1, 0});
// }
// void upd(int v, int val)
// {
// tree[v].mn = (tree[v].mn + val) % mod;
// tree[v].mx = (tree[v].mx + val) % mod;
// assert(tree[v].mn <= tree[v].mx);
// }
// void push(int v, int lv, int rv)
// {
// if (rv - lv == 1 or tree[v].op == 0)
// return;
// upd(v * 2 + 1, tree[v].op);
// upd(v * 2 + 2, tree[v].op);
// tree[v].op = 0;
// }
// void merge(int v)
// {
// tree[v].mn = min(tree[v * 2 + 1].mn, tree[v * 2 + 2].mn);
// tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
// }
// void set(int pos, int val, int v, int lv, int rv)
// {
// push(v, lv, rv);
// if (rv - lv == 1)
// {
// tree[v].mn = tree[v].mx = val;
// return;
// }
// int m = (lv + rv) >> 1;
// if (pos < m)
// set(pos, val, v * 2 + 1, lv, m);
// else
// set(pos, val, v * 2 + 2, m, rv);
// merge(v);
// }
// void set(int pos, int val)
// {
// set(pos, val, 0, 0, sz);
// }
// void add(int )
// };
struct DSU
{
vector<int> p;
void init(int n)
{
p.resize(n);
for (int i = 0; i < n; ++i)
p[i] = i;
}
int getR(int v)
{
return v == p[v] ? v : p[v] = getR(p[v]);
}
void merge(int a, int b)
{
assert(a == getR(a));
assert(b == getR(b));
p[b] = a;
}
};
struct test
{
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
vector<segTreeSum> tree(2);
tree[0].init(n);
tree[1].init(n);
for (int i = 0; i < n; ++i)
{
char x;
cin >> x;
a[i] = x == 'R';
tree[a[i]].set(i, i + 1, 1);
}
vector<int> P(m);
for (int i = 0; i < m; ++i)
{
cin >> P[i];
P[i]--;
}
bool good = true;
int cntG = 0;
{
bool wasOne = false;
for (int i = 0; i < n; ++i)
{
if (a[i])
{
cntG = i + 1;
if (wasOne)
good = false;
}
else
{
wasOne = true;
}
}
}
if (!good)
{
int q;
cin >> q;
auto bf = a;
for (int i = 0; i < q; ++i)
{
int l, r;
cin >> l >> r;
--l, --r;
{
for (int i = 0; i < n; ++i)
{
tree[a[i]].set(i, i + 1, 1);
tree[1 - a[i]].set(i, i + 1, 0);
}
for (int i = l; i <= r; ++i)
{
int p = P[i];
tree[1].set(p, p + 1, 1);
tree[0].set(p, p + 1, 0);
int c1 = tree[0].get(p, n);
int c2 = tree[1].get(0, p + 1);
if (c1 >= c2)
{
int leftMostPos = tree[0].getKthFromStart(tree[0].get(0, p + 1) + c2 - 1);
tree[0].set(0, leftMostPos + 1, 0);
tree[1].set(0, leftMostPos + 1, 1);
}
else
{
int rightMostPos = tree[1].getKthFromEnd(tree[1].get(p + 1, n) + c1);
tree[0].set(rightMostPos, n, 1);
tree[1].set(rightMostPos, n, 0);
}
}
cout << tree[1].get(0, n) << "\n";
}
}
}
else
{
int q;
cin >> q;
vector<int> ans(q);
vector<vector<pii>> qId(m);
for (int i = 0; i < q; ++i)
{
int l, r;
cin >> l >> r;
--l, --r;
qId[r].pb({l, i});
}
vector<int> res(m);
vector<pii> was(n + 1, {-1, -1});
vector<pii> uniqueVals;
DSU dsu;
dsu.init(m);
for (int i = 0; i < m; ++i)
{
vector<pii> nvals;
int p = P[i];
for (auto &[c1, v] : uniqueVals)
{
c1 = (p + (p >= c1) + c1 + 1) % (n + 1);
if (was[c1].f == i)
{
dsu.merge(was[c1].s, v);
}
else
{
res[v] = c1;
nvals.pb({c1, v});
was[c1] = {i, v};
}
}
uniqueVals = nvals;
assert(uniqueVals.size() <= n + 10);
int curVal = (P[i] + (P[i] >= cntG) + cntG + 1) % (n + 1);
uniqueVals.push_back({curVal, i});
res[i] = curVal;
for (auto [l, id] : qId[i])
{
ans[id] = res[dsu.getR(l)];
}
}
for (int i = 0; i < q; ++i)
cout << ans[i] << "\n";
}
}
};
main()
{
test t;
t.solve();
}
