#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec(tail...); return v; } long long max(long long a, int b){return std::max(a, (long long)b);} long long max(int a, long long b){return std::max((long long)a, b);} long long min(long long a, int b){return std::min(a, (long long)b);} long long min(int a, long long b){return std::min((long long)a, b);} long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;} template struct safe_vector : std::vector{ using std::vector::vector; T& operator [](size_t i){return this->at(i);} }; template struct safe_array : std::array{ using std::array::array; T& operator [](size_t i){return this->at(i);} }; ll ceil_div(ll x, ll y){ assert(y > 0); return (x + (x > 0 ? y - 1 : 0)) / y; } ll floor_div(ll x, ll y){ assert(y > 0); return (x + (x > 0 ? 0 : -y + 1)) / y; } void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } template struct accumulate1d{ std::vector sum; accumulate1d(){} accumulate1d(const std::vector &v): sum(v){ for(int i = 1; i < v.size(); i++) sum[i] = sum[i - 1] + v[i]; } // [0, r)の和, 範囲外の部分は全て単位元 Val query(int r){ r = std::min(r, (int)sum.size()); if(r <= 0) return 0; return sum[r - 1]; } // [l, r)の和, 範囲外の部分は全て単位元 Val query(int l, int r){ l = std::max(l, 0); r = std::min(r, (int)sum.size()); if(r <= l) return 0; return (l == 0 ? sum[r - 1] : (sum[r - 1] - sum[l - 1])); } void push_back(Val x){ Val y = (sum.empty() ? 0 : sum.back()); sum.push_back(y + x); } void pop_back(){ assert(!sum.empty()); sum.pop_back(); } // [0, k]がx以上になる最小インデックス, ない場合はn int lower_bound(Val x){ return std::lower_bound(sum.begin(), sum.end(), x) - sum.begin(); } // [0, k]がxより大きくなる最小インデックス, ない場合はn int upper_bound(Val x){ return std::upper_bound(sum.begin(), sum.end(), x) - sum.begin(); } }; // F := 普通の区間クエリ // G := 合成 template T cicle_range_query(long long N, long long l, long long r, std::function F, std::function G){ long long d = l / N; l -= d * N; r -= d * N; if(r <= N) return F(l, r); T res = F(l, N); r -= N; d = r / N; r -= d * N; // pow if(d){ T a, b = F(0, N); bool first = true; while(d){ if(d & 1){ if(first){ a = b; first = false; }else{ a = G(a, b); } } b = G(b, b); d >>= 1; } res = G(res, a); } if(r) res = G(res, F(0, r)); return res; } int main(){ io_init(); int n, q; std::cin >> n >> q; string s; std::cin >> s; // x = h, y = wなら終了 // x = hなら右 // y = wなら下 // Siの通りに移動してi++ vector _R(n, 0), _D(n, 0); range(i, 0, n){ if(s[i] == 'R') _R[i]++; else _D[i]++; } accumulate1d R(_R), D(_D); auto sum = [](ll a, ll b) -> ll { return a + b; }; auto queryD = [&](ll a, ll b) -> ll {return D.query(a, b);}; auto queryR = [&](ll a, ll b) -> ll {return R.query(a, b);}; auto getD = [&](ll a, ll b) -> ll { return cicle_range_query(n, a, b, queryD, sum); }; auto getR = [&](ll a, ll b) -> ll { return cicle_range_query(n, a, b, queryR, sum); }; range(i, 0, q){ int h, w, p; std::cin >> h >> w >> p; ll l = 0, r = 2000000000; while(r - l > 1){ ll m = (l + r) / 2; // Sp.....S{p+m-1}にDがh個以上またはRがw個以上あるか if(getD(p, p + m) >= h || getR(p, p + m) >= w){ r = m; }else{ l = m; } } std::cout << (p + r) % n << '\n'; } }