#include <bits/stdc++.h>
using namespace std;
int gdzie[120007];
int n;
bool debug = false;
bool debug2 = false;
struct przedzial
{
int l, r, ile;
bool operator < (przedzial a) const
{
return l < a.l;
}
};
vector<przedzial> drz[262150];
vector<przedzial> lacz_przedzialy(const vector<przedzial>& pierwszy, const vector<przedzial>& drugi)
{
vector<przedzial> wynik;
/*przedzial szukane;
szukane.l = 2;
szukane.r = 1;
szukane.ile = 2;*/
if (pierwszy.size() == 0)
{
wynik = drugi;
return wynik;
}
if (drugi.size() == 0)
{
wynik = pierwszy;
return wynik;
}
for (auto x : pierwszy)
{
int nowel, nower;
nowel = (x.l + x.ile) % (n + 1);
nower = (x.r + x.ile) % (n + 1);
if(debug)
{
cout << "nowe: " << nowel << " " << nower << endl;
}
if (nowel <= nower)
{
przedzial tempo;
tempo.l = nowel;
tempo.r = -1;
auto it = --upper_bound(drugi.begin(), drugi.end(), tempo);
/*if (it != drugi.begin())
{
it--;
}*/
if(debug)
{
cout << "wyw " << nowel << " " << nower << " " << x.ile << endl;
}
while (it != drugi.end() && nowel <= nower)
{
if(debug)
{
cout << "cur " << nowel << " " << nower << endl;
cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
}
int nowel2 = max(nowel, it->l);
int nower2 = min(nower, it->r);
nowel = nower2 + 1;
if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
{
wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
}
/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
{
cout << "1" << endl;
}*/
it++;
}
}
else
{
int popnowe = nower;
nower = n;
przedzial tempo;
tempo.l = nowel;
tempo.r = -1;
auto it = --upper_bound(drugi.begin(), drugi.end(), tempo);
/*if (it != drugi.begin())
{
it--;
}*/
if(debug)
{
cout << "wyw " << nowel << " " << nower << " " << x.ile << endl;
}
while (it != drugi.end() && nowel <= nower)
{
int nowel2 = max(nowel, it->l);
int nower2 = min(nower, it->r);
if(debug)
{
cout << "cur " << nowel << " " << nower << endl;
cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
}
nowel = nower2 + 1;
if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
{
wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
}
/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
{
//cout << x.l << " " << x.r << " " << x.ile << endl;
//cout << it->l << " " << it->r << endl;
//cout << nowel2 << " " << nower2 << endl;
//cout << nowel << " " << nower << endl;
//cout << "2" << endl;
}*/
it++;
}
nowel = 0;
nower = popnowe;
tempo.l = nowel;
tempo.r = -1;
it = --upper_bound(drugi.begin(), drugi.end(), tempo);
/*if (it != drugi.begin())
{
it--;
}*/
if(debug)
{
cout << "wyw " << nowel << " " << nower << " " << x.ile << endl;
}
while (it != drugi.end() && nowel <= nower)
{
if(debug)
{
cout << "cur " << nowel << " " << nower << endl;
cout << "it " << it->l << " " << it->r << " " << it->ile << endl;
}
/*if(pierwszy[0].l == 0 && pierwszy[0].r == 4 && nower == 4)
{
cout << it->l << " " << it->r << " " << it->ile << endl;
}*/
int nowel2 = max(nowel, it->l);
int nower2 = min(nower, it->r);
nowel = nower2 + 1;
if((nowel2 - x.ile + (n + 1)) % (n + 1) <= (nower2 - x.ile + (n + 1)) % (n + 1))
{
wynik.push_back({ (nowel2 - x.ile + (n + 1)) % (n + 1), (nower2 - x.ile + (n + 1)) % (n + 1), (x.ile + it->ile) % (n + 1) });
}
/*if(wynik[wynik.size() - 1].l == szukane.l && wynik[wynik.size() - 1].r == szukane.r && wynik[wynik.size() - 1].ile == szukane.ile)
{
cout << "3" << endl;
}*/
it++;
}
}
}
sort(wynik.begin(), wynik.end());
if(debug2)
{
for(auto x : pierwszy)
{
cout << x.l << " " << x.r << " " << x.ile << endl;
}
cout << endl;
for(auto x : drugi)
{
cout << x.l << " " << x.r << " " << x.ile << endl;
}
cout << endl;
for(auto x : wynik)
{
cout << x.l << " " << x.r << " " << x.ile << endl;
}
cout << endl;
}
return wynik;
}
void licz(int cur)
{
if (cur >= 131072)
{
return;
}
licz(2 * cur);
licz(2 * cur + 1);
drz[cur] = lacz_przedzialy(drz[2 * cur], drz[2 * cur + 1]);
}
vector<pair<int, int>> gdzie_kon;
void przedzial(int l, int r, int curl, int curr, int gdzie)
{
if (curl > r || curr < l)
{
return;
}
if (l <= curl && r >= curr)
{
gdzie_kon.push_back({ curl, gdzie });
}
else
{
przedzial(l, r, curl, (curl + curr) / 2, gdzie * 2);
przedzial(l, r, (curl + curr) / 2 + 1, curr, gdzie * 2 + 1);
}
}
int policz(int stan, int l, int r)
{
gdzie_kon.clear();
przedzial(l, r, 1, 131072, 1);
sort(gdzie_kon.begin(), gdzie_kon.end());
for (auto x : gdzie_kon)
{
//cout << x.second << endl;
/*for(auto y : drz[x.second])
{
//cout << y.l << " " << y.r << " " << y.ile << endl;
}*/
//cout << endl;
int lbin = 0, rbin = drz[x.second].size() - 1, gdzie;
while (lbin <= rbin)
{
int sr = lbin + (rbin - lbin) / 2;
if (stan < drz[x.second][sr].l)
{
rbin = sr - 1;
}
else if (stan > drz[x.second][sr].r)
{
lbin = sr + 1;
}
else
{
lbin = rbin + 7;
gdzie = sr;
}
}
stan += drz[x.second][gdzie].ile;
stan %= (n + 1);
}
return stan;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, q, l, r, pref = 0;
string s;
cin >> n >> m >> s;
for (int i = 0; i < n; i++)
{
if (s[i] == 'R')
{
pref++;
}
else
{
i = n + 4;
}
}
for (int i = 0; i < m; i++)
{
cin >> gdzie[i];
}
for (int i = 0; i < m; i++)
{
if (gdzie[i] != 0)
{
drz[i + 131072].push_back({ 0, gdzie[i] - 1, gdzie[i] + 1 });
}
drz[i + 131072].push_back({ gdzie[i], n, gdzie[i] });
}
licz(1);
/*for(auto x : drz[65539])
{
cout << x.l << " " << x.r << " " << x.ile << endl;
}*/
cin >> q;
while (q--)
{
int stan;
cin >> l >> r;
stan = policz(pref, l, r);
cout << stan << endl;
}
return 0;
}
