#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))
#define repInAmp2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
constexpr int maxn = 12e4 + 7, maxTreeBase = 1 << 17, maxLog = 16, inf = 1e9 + 7;
int n, m;
bool ogRight[maxn], myRight[maxn];
int arr[maxn], prefSum[maxn];
vector<pair<pair<int, int>, int>> t[2 * maxTreeBase];
int treeBase;
int maxH1[maxn][maxLog], minH2[maxn][maxLog];
ll prefSumH1[maxn], prefSumH2[maxn];
constexpr int bufSize = 5* (60 + maxn * 2 + maxn * 10 + maxn * 2 * 10);
char buffer[bufSize];
int bufI;
void initBuffer() {
fread_unlocked(buffer, sizeof(char), bufSize, stdin);
}
void getInt(int& x) {
while(buffer[bufI] > '9' || buffer[bufI] < '0') bufI++;
x = 0;
while(buffer[bufI] <= '9' && buffer[bufI] >= '0') x = 10 * x + buffer[bufI] - '0', bufI++;
}
inline int getMaxH1(int l, int r) {
if(l == r) return maxH1[l][0];
int k = 31 - __builtin_clz(r - l + 1);
return max(maxH1[l][k], maxH1[r - (1 << k) + 1][k]);
}
inline int getMinH2(int l, int r) {
if(l == r) return minH2[l][0];
int k = 31 - __builtin_clz(r - l + 1);
return min(minH2[l][k], minH2[r - (1 << k) + 1][k]);
}
inline int truePrefSum(int l, int r, int x) {
if(x <= l) return x;
if(x >= r) return l + 1 + prefSum[r] - prefSum[l + 1];
return l + 1 + prefSum[x] - prefSum[l + 1];
}
inline int cntRight(int l, int r, int il, int ir) {
return truePrefSum(l, r, ir + 1) - truePrefSum(l, r, il);
}
inline int cntLeft(int l, int r, int il, int ir) {
return (ir - il + 1) - cntRight(l, r, il, ir);
}
pair<int, int> f(int l, int r, int a) {
DC << "f({" << l << ' ' << r << "}, " << a << "): " << eol << " ";
int bl = cntRight(l, r, 0, a - 1);
int br = cntLeft(l, r, a + 1, n - 1);
DC << " bl = " << bl << "; br = " << br << eol;
if(bl >= br) {
// wylatujemy z prawej
// pierwsze br wsrod bl przechodzi na br
// szukamy ostatniego miejsca gdzie cntRight(0, a - 1) + br < bl
DC << " przekabacamy " << br << " typow z lewej " << eol;
int p = 0, s, k = a;
bool xd = false;
rep(xdd, 1, 2) if(p < a - xdd && cntRight(l, r, 0, a - 1 - xdd) + br < bl) { p = a - xdd; xd = true; break; }
while(k - p > 1) {
s = (p + k) / 2;
if(cntRight(l, r, 0, s - 1) + br < bl) p = s;
else k = s;
}
if(bl > br) p++;
return {min(l, p - 1), p};
}
else {
// wylatujemy z lewej
// pierwsze bl + 1 wsrod br przechodzi na bl
// szukamy pierwszego miejsca gdzie cntLeft(a + 1, n - 1) + bl + 1 <= br
DC << " przekabacamy " << bl + 1 << " typow z prawej " << eol;
int p = a, s, k = n - 1;
bool xd = false;
rep(xdd, 1, 2) if(k > a + xdd && cntLeft(l, r, a + 1 + xdd, n - 1) + bl + 1 <= br) { k = a + xdd; xd = true; break; }
while(k - p > 1) {
s = (p + k) / 2;
if(cntLeft(l, r, s + 1, n - 1) + bl + 1 <= br) k = s;
else p = s;
}
return {k, max(k + 1, r)};
}
return {0, 0};
}
void calcTree() {
DC << "Builbimg tree" << eol;
treeBase = 1 << (32 - __builtin_clz(m));
rep(i, 0, m) t[i + treeBase] = { {{0, arr[i] - 1}, arr[i] + 1}, {{arr[i], n}, arr[i]}};
rep(i, m, treeBase) t[i + treeBase] = { {{0, n}, 0} };
repD(i, treeBase - 1, 0) {
vector<pair<pair<int, int>, int>> treatSeparately;
repIn2(lr, add, t[i * 2]) {
auto [l, r] = lr;
auto nl = (l + add) % (n + 1), nr = (r + add) % (n + 1);
if(nl > nr) { treatSeparately.pb({{l, ((n - add) % (n + 1) + n + 1) % (n + 1)}, add}); treatSeparately.pb({{((-add) % (n + 1) + n + 1) % (n + 1), r}, add}); continue; }
auto it = ranges::upper_bound(t[2 * i + 1], make_pair(make_pair(nr, (int)1e9), (int)1e9));
if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
auto start = it;
do {
it--;
auto [l2, r2] = it -> first;
if(r2 < nl || nr < l2) break;
t[i].pb(make_pair(make_pair(((max(l2, nl) - add) % (n + 1) + n + 1) % (n + 1), ((min(nr, r2) - add) % (n + 1) + n + 1) % (n + 1)), (add + it -> second) % (n + 1)));
if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
} while(it != start);
}
repIn2(lr, add, treatSeparately) {
auto [l, r] = lr;
auto nl = (l + add) % (n + 1), nr = (r + add) % (n + 1);
if(nl > nr) { treatSeparately.pb({{l, ((n - add) % (n + 1) + n + 1) % (n + 1)}, add}); treatSeparately.pb({{((-add) % (n + 1) + n + 1) % (n + 1), r}, add}); continue; }
auto it = ranges::upper_bound(t[2 * i + 1], make_pair(make_pair(nr, (int)1e9), (int)1e9));
if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
auto start = it;
do {
it--;
auto [l2, r2] = it -> first;
if(r2 < nl || nr < l2) break;
t[i].pb(make_pair(make_pair(((max(l2, nl) - add) % (n + 1) + n + 1) % (n + 1), ((min(nr, r2) - add) % (n + 1) + n + 1) % (n + 1)), (add + it -> second) % (n + 1)));
if(it == t[2 * i + 1].begin()) it = t[2 * i + 1].end();
} while(it != start);
}
ranges::stable_sort(t[i]);
}
DEBUG {
DC << "Tree built /\\" << eol << eol;
}
}
vector<int> basesL, basesR;
int queryTree(int l, int r, int startState) {
DC << "Q " << l << ' ' << r << " startState " << startState << eol;
l += treeBase;
r += treeBase;
basesL.clear(); basesR.clear();
basesL.pb(l);
if(l != r) basesR.pb(r);
while(l / 2 != r / 2) {
if(l % 2 == 0) basesL.pb(l + 1);
if(r % 2 == 1) basesR.pb(r - 1);
l /= 2;
r /= 2;
}
repIn(i, basesL) {
auto it = ranges::upper_bound(t[i], make_pair(make_pair(startState, (int)1e9), (int)1e9));
if(it == t[i].begin()) it = t[i].end();
it--;
DC << (it -> first.first) << ' ' << (it -> first.second) << " adds " << (it -> second) << " -> (" << startState << " + " << (it -> second) << ") % " << n + 1 << " = ";
startState = (startState + it -> second) % (n + 1);
DC << startState << eol;
}
ranges::reverse(basesR);
repIn(i, basesR) {
auto it = ranges::upper_bound(t[i], make_pair(make_pair(startState, (int)1e9), (int)1e9));
if(it == t[i].begin()) it = t[i].end();
it--;
DC << (it -> first.first) << ' ' << (it -> first.second) << " adds " << (it -> second) << " -> (" << startState << " + " << (it -> second) << ") % " << n + 1 << " = ";
startState = (startState + it -> second) % (n + 1);
DC << startState << eol;
}
return startState;
}
int binsearch(int start, int end, int l, int r) {
// szukamy ostatniego miejsca gdzie maxH1 <= l && minH2 >= r oraz sie nie spotkaja
int p = start - 1, s, k = end;
while(k - p > 1) {
s = (p + k) / 2;
ll sumH1 = prefSumH1[s + 1] - prefSumH1[start];
ll sumH2 = prefSumH2[s + 1] - prefSumH2[start];
if(getMaxH1(start, s) > l || getMinH2(start, s) < r || l + sumH1 >= r - sumH2 || cntLeft(l, r, l + 1, (l + r) / 2) < sumH1 || cntRight(l, r, (l + r) / 2 + 1, r) < sumH2) k = s;
else p = s;
}
return p;
}
int main() {
initBuffer();
getInt(n); getInt(m);
char c;
while((buffer[bufI] != 'R' && buffer[bufI] != 'B') && (buffer[bufI] != '>' && buffer[bufI] != '<')) bufI++;
rep(i, 0, n) c = buffer[bufI++], ogRight[i] = (c == 'R') || (c == '>');
rep(i, 0, n) prefSum[i + 1] = prefSum[i] + ogRight[i];
rep(i, 0, m) getInt(arr[i]);
int h1Cutoff = n / 2;
rep(i, 0, m) {
prefSumH1[i + 1] = prefSumH1[i];
prefSumH2[i + 1] = prefSumH2[i];
if(arr[i] <= h1Cutoff) {
prefSumH1[i + 1] += arr[i];
maxH1[i][0] = arr[i] - 1;
minH2[i][0] = inf;
}
else {
prefSumH2[i + 1] += n - arr[i];
minH2[i][0] = arr[i] - 1;
maxH1[i][0] = -inf;
}
}
rep(k, 1, maxLog) rep(i, 0, m) maxH1[i][k] = max(maxH1[i][k - 1], maxH1[min(m - 1, i + (1 << (k - 1)))][k - 1]);
rep(k, 1, maxLog) rep(i, 0, m) minH2[i][k] = min(minH2[i][k - 1], minH2[min(m - 1, i + (1 << (k - 1)))][k - 1]);
calcTree();
string output, str;
pair<int, int> lrIni = {-1, n};
while(lrIni.first < n && ogRight[lrIni.first + 1]) lrIni.first++;
while(lrIni.second && !ogRight[lrIni.second - 1]) lrIni.second--;
int q;
getInt(q);
rep(i, 0, q) {
int start, end;
getInt(start); getInt(end);
start--; end--;
auto [l, r] = lrIni;
bool lastFound = false;
while(start <= end) {
if(l + 1 == r) {
DC << "Spotkali sie" << eol;
break;
}
int p = start - 1;
if(!lastFound) {
int s = start;
ll sumH1 = prefSumH1[s + 1] - prefSumH1[start];
ll sumH2 = prefSumH2[s + 1] - prefSumH2[start];
if(!(getMaxH1(start, s) > l || getMinH2(start, s) < r || l + sumH1 >= r - sumH2 || cntLeft(l, r, l + 1, (l + r) / 2) < sumH1 || cntRight(l, r, (l + r) / 2 + 1, r) < sumH2)) p = binsearch(start, end, l, r);
}
DC << "Z lr " << l << ' ' << r << " przedzial krasnoludkow " << start << ' ' << end << " binsearch wyplul " << p << eol;
if(p == start - 1) {
auto lr = f(l, r, arr[start] - 1);
l = lr.first; r = lr.second;
lastFound = false;
}
else {
lastFound = true;
// szukamy pierwszego miejsca gdzie cntLeft(l + 1, x) >= sumH1(start, p)
ll sumH1 = prefSumH1[p + 1] - prefSumH1[start];
int pp = l - 1, ss, kk = r - 1;
while(kk - pp > 1) {
ss = (pp + kk) / 2;
if(max(0, cntLeft(l, r, l + 1, ss)) >= sumH1) kk = ss;
else pp = ss;
}
l = kk;
// szukamy ostatniego miejsca gdzie cntRight(x, r - 1) >= sumH2(start, p)
ll sumH2 = prefSumH2[p + 1] - prefSumH2[start];
pp = 0, kk = r + 1;
while(kk - pp > 1) {
ss = (pp + kk) / 2;
if(max(0, cntRight(l, r, ss, r - 1)) >= sumH2) pp = ss;
else kk = ss;
}
r = pp;
if(l >= r) l = r - 1;
start = p;
}
DC << "Nowe lr: " << l << ' ' << r << eol;
start++;
}
int ans = (start <= end) ? queryTree(start, end, l + 1) : cntRight(l, r, 0, n - 1);
str.clear();
while(ans) str += (char)(ans % 10 + '0'), ans /= 10;
if(str.empty()) str = '0';
ranges::reverse(str);
str.pb('\n');
output += str;
}
fwrite_unlocked(output.c_str(), sizeof(char), output.size(), stdout);
}
