/* -*- coding: utf-8 -*- * * 2716.cc: No.2716 Falcon Method - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 200000; const int INF = 1 << 30; /* typedef */ /* global variables */ char s[MAX_N + 4]; int xss[MAX_N * 2 + 1], yss[MAX_N * 2 + 1]; /* subroutines */ /* main */ int main() { int n, qn; scanf("%d%d%s", &n, &qn, s); int n2 = n * 2; for (int i = 0; i < n2; i++) { xss[i + 1] = xss[i] + (s[i % n] == 'D' ? 1 : 0); yss[i + 1] = yss[i] + (s[i % n] == 'R' ? 1 : 0); } while (qn--) { int h, w, p; scanf("%d%d%d", &h, &w, &p); int ex = (xss[n] == 0) ? INF : (h - 1) / xss[n]; int ey = (yss[n] == 0) ? INF : (w - 1) / yss[n]; int e = min(ex, ey); h -= e * xss[n], w -= e * yss[n]; //printf(" h=%d, w=%d\n", h, w); int k0 = p, k1 = p + n + 1; while (k0 + 1 < k1) { int k = (k0 + k1) / 2; if (xss[k] - xss[p] < h && yss[k] - yss[p] < w) k0 = k; else k1 = k; } printf("%d\n", k1 % n); } return 0; }