#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
string s;
struct c{
int a;
int b;
int dod;
};
struct d{
vector<c> swapy;
};
vector<int> krasnoludki;
const int MAXN = 2e5 + 5;
const int base = 1 << 17;
d drugaczesc[2 * base];
int M;
bool comp(const c &c1, const c &c2){
if(c1.a != c2.a){
return c1.a < c2.a;
}
return false;
}
int drugiwyn(int w, int a, int b, int akt_a, int akt_b, int curr){
if(a <= akt_a and akt_b <= b){
int p = 0;
int k = drugaczesc[w].swapy.size() - 1;
while(p != k){
int sr = (p + k) / 2;
if(drugaczesc[w].swapy[sr].b < curr){
p = sr + 1;
}
else{
k = sr;
}
}
return (curr + drugaczesc[w].swapy[p].dod) % M;
}
if(akt_a > b or akt_b < a) return curr;
int mid = (akt_a + akt_b) / 2;
curr = drugiwyn(2 * w, a, b, akt_a, mid, curr);
curr = drugiwyn(2 * w + 1, a, b, mid + 1, akt_b, curr);
return curr;
}
struct e{
int sR;
int sB;
};
e drzew[2 * base];
int ans[MAXN];
int iloscR(int w, int a, int b, int akt_a, int akt_b){
if(a > b) return 0;
if(a <= akt_a and akt_b <= b){
return drzew[w].sR;
}
if(akt_a > b or akt_b < a) return 0;
int mid = (akt_a + akt_b) / 2;
return iloscR(2 * w, a, b, akt_a, mid) + iloscR(2 * w + 1, a, b, mid + 1, akt_b);
}
int iloscB(int w, int a, int b, int akt_a, int akt_b){
if(a > b) return 0;
if(a <= akt_a and akt_b <= b){
return drzew[w].sB;
}
if(akt_a > b or akt_b < a) return 0;
int mid = (akt_a + akt_b) / 2;
return iloscB(2 * w, a, b, akt_a, mid) + iloscB(2 * w + 1, a, b, mid + 1, akt_b);
}
int ktaB(int w, int akt_a, int akt_b, int curr, int cel){
if(akt_a == akt_b) return akt_a;
int mid = (akt_a + akt_b) / 2;
if(drzew[2 * w].sB + curr < cel){
return ktaB(2 * w + 1, mid + 1, akt_b, curr + drzew[2 * w].sB, cel);
}
else{
return ktaB(2 * w, akt_a, mid, curr, cel);
}
}
int ktaR(int w, int akt_a, int akt_b, int curr, int cel){
if(akt_a == akt_b) return akt_a;
int mid = (akt_a + akt_b) / 2;
if(drzew[2 * w + 1].sR + curr < cel){
return ktaR(2 * w, akt_a, mid, curr + drzew[2 * w + 1].sR, cel);
}
else{
return ktaR(2 * w + 1, mid + 1, akt_b, curr, cel);
}
}
pair<int,int> dodajp(int pref, int suff, int ile, int n){
int pocz = pref;
int kon = n - suff + 1;
int v = iloscB(1, pocz + 1, kon - 1, 1, base);
if(ile >= v){
pocz = kon - 1;
ile -= v;
pocz = (pocz + ile) % M;
kon = pocz + 1;
return {pocz, n - pocz};
}
v = iloscB(1, 1, pocz, 1, base);
return {ktaB(1, 1, base, 0, v + ile + 1) - 1, suff};
}
pair<int,int> dodajk(int pref, int suff, int ile, int n){
int pocz = pref;
int kon = n - suff + 1;
int v = iloscR(1, pocz + 1, kon - 1, 1, base);
if(ile >= v){
ile -= v;
pocz = (pocz + ile + 1) % M;
kon = pocz + 1;
return {pocz, n - pocz};
}
v = iloscR(1, kon, base, 1, base);
return {pocz, n - ktaR(1, 1, base, 0, v + ile + 1)};
}
pair<int,int> dodajs(int pref, int suff, int mid, int n){
int pocz = pref;
int kon = n - suff + 1;
int iR1 = pref;
int iR2 = iloscR(1, pocz + 1, mid - 1, 1, base);
int iB1 = suff;
int iB2 = iloscB(1, mid + 1, kon - 1, 1, base);
int s1 = iR1 + iR2;
int s2 = iB1 + iB2;
if(s1 >= s2){
if(s2 >= iR2){
pocz = pref - (s2 - iR2);
return {pocz, n - pocz};
}
else{
int v = iloscR(1, mid, base, 1, base);
return {pocz, n - ktaR(1, 1, base, 0, v + s2 + 1)};
}
}
else{
if(s1 >= iB2){
pocz = kon - 1 + (s1 - iB2);
return {pocz, n - pocz};
}
else{
int v = iloscB(1, 1, mid, 1, base);
return {ktaB(1, 1, base, 0, v + s1 + 2) - 1, suff};
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
M = n + 1;
int a, b;
cin >> s;
int p1 = 0;
int s1 = 0;
for(int i = 0; i < n; ++i){
if(s[i] == '>' or s[i] == 'R'){
p1++;
}
else{
break;
}
}
for(int i = n - 1; i >= 0; --i){
if(s[i] == '<' or s[i] == 'B'){
s1++;
}
else{
break;
}
}
//liczenie drzewa strzalek
{
for(int i = 0; i < n; ++i){
if(s[i] == '>' or s[i] == 'R'){
drzew[i + base] = {1, 0};
}
else{
drzew[i + base] = {0, 1};
}
}
for(int i = base - 1; i > 0; --i){
drzew[i] = {drzew[2 * i].sR + drzew[2 * i + 1].sR, drzew[2 * i].sB + drzew[2 * i + 1].sB};
}
}
//liczenie 2 czesci
{
krasnoludki.push_back(-1);
for(int i = 0; i < m; ++i){
cin >> a;
krasnoludki.push_back(a);
drugaczesc[i + base].swapy = {{0, a - 1, a + 1}, {a, n, a}};
}
for(int i = m + base; i < 2 * base; ++i){
drugaczesc[i].swapy = {{0, n, 0}};
}
for(int i = base - 1; i > 0; --i){
//cout << i << " i\n";
auto v1 = drugaczesc[2 * i].swapy;
auto v2 = drugaczesc[2 * i + 1].swapy;
vector<c> odp;
auto policz = [&](int a, int b, int dod){
int p = 0;
int k = v2.size() - 1;
while(p != k){
int sr = (p + k) / 2;
if(v2[sr].b < a){
p = sr + 1;
}
else{
k = sr;
}
}
if(v2[p].a <= a and b <= v2[p].b){
//cout << (a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[p].dod << " if1\n";
odp.push_back({(a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[p].dod});
return;
}
//cout << a << " " << b << " ab\n";
int curr = p;
//cout << (a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " lewo\n";
odp.push_back({(a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
curr++;
while(v2[curr].a <= b){
if(v2[curr].b <= b){
//cout << (v2[curr].a - dod + 5 * M) % M << " " << (v2[curr].b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " mid\n";
odp.push_back({(v2[curr].a - dod + 5 * M) % M, (v2[curr].b - dod + 5 * M) % M, dod + v2[curr].dod});
}
else{
//cout << (v2[curr].a - dod + 5 * M) % M << " " << (b - dod + 5 * M) % M << " " << dod + v2[curr].dod << " prawo\n";
odp.push_back({(v2[curr].a - dod + 5 * M) % M, (b - dod + 5 * M) % M, dod + v2[curr].dod});
break;
}
if(curr == v2.size() - 1) break;
curr++;
}
return;
};
for(auto u : v1){
int valdod = (u.a + u.dod) % M;
int valkon = (u.b + u.dod) % M;
//cout << valdod << " " << valkon << " pk\n";
if(valdod <= valkon){
policz(valdod, valkon, u.dod);
}
else{
policz(valdod, n, u.dod);
policz(0, valkon, u.dod);
}
}
vector<c> tmp;
for(auto u : odp){
if(u.a > u.b){
tmp.push_back({0, u.b, u.dod});
tmp.push_back({u.a, n, u.dod});
}
else{
tmp.push_back(u);
}
tmp.back().dod %= M;
}
odp = tmp;
// for(auto u : odp){
// cout << u.a << " " << u.b << " " << u.dod << " po zlozeniu\n";
// }
sort(odp.begin(),odp.end(),comp);
drugaczesc[i].swapy = odp;
}
}
int q;
cin >> q;
for(int i = 0; i < q; ++i){
int a, b;
cin >> a >> b;
//cout << a << " " << b << " ab\n";
int pref = p1;
int suff = s1;
bool czy = false;
while(a <= b){
if(pref + suff == n){
cout << drugiwyn(1, a, b, 1, base, pref) << "\n";
czy = true;
break;
}
if(krasnoludki[a] <= pref){
auto k = dodajp(pref, suff, krasnoludki[a], n);
pref = k.first;
suff = k.second;
}
else if(krasnoludki[a] > n - suff){
auto k = dodajk(pref, suff, n - krasnoludki[a], n);
pref = k.first;
suff = k.second;
}
else{
auto k = dodajs(pref, suff, krasnoludki[a], n);
pref = k.first;
suff = k.second;
}
a++;
}
//cout << pref << " " << suff << " ps\n";
if(czy == true) continue;
if(pref + suff == n){
cout << pref << "\n";
}
else{
int pocz = pref;
int kon = n - suff + 1;
cout << pref + iloscR(1, pocz + 1, kon - 1, 1, base) << "\n";
}
}
return 0;
}
