fn main() { let (n, q) = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) }; let s: Vec = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().chars().collect() }; let hwp: Vec<_> = (0..q) .map(|_| { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) }) .collect(); // 文字列Sの通りに進んだときの累積距離 let mut prefix_sum = vec![(0, 0); n + 1]; for (i, &c) in s.iter().enumerate() { prefix_sum[i + 1] = prefix_sum[i]; if c == 'D' { prefix_sum[i + 1].0 += 1; } else { prefix_sum[i + 1].1 += 1; } } let calc_progress = |left: usize, right: usize| { ( prefix_sum[right].0 - prefix_sum[left].0, prefix_sum[right].1 - prefix_sum[left].1, ) }; let solve = |mut h: usize, mut w: usize, p: usize| { let progress_from_p_to_n = calc_progress(p, n); // 文字列の終端までにグリッドの端に辿り着く場合 if progress_from_p_to_n.0 >= h || progress_from_p_to_n.1 >= w { let mut ok = n; let mut ng = p; while ok.abs_diff(ng) > 1 { let mid = (ok + ng) / 2; let progress = calc_progress(p, mid); if progress.0 >= h || progress.1 >= w { ok = mid; } else { ng = mid; } } return ok % n; } h -= progress_from_p_to_n.0; w -= progress_from_p_to_n.1; let progress_from_0_to_n = calc_progress(0, n); let cycle_num = match (progress_from_0_to_n.0 == 0, progress_from_0_to_n.1 == 0) { (true, true) => unreachable!(), (true, false) => w / progress_from_0_to_n.1, (false, true) => h / progress_from_0_to_n.0, (false, false) => (h / progress_from_0_to_n.0).min(w / progress_from_0_to_n.1), }; h -= progress_from_0_to_n.0 * cycle_num; w -= progress_from_0_to_n.1 * cycle_num; if h == 0 || w == 0 { return 0; } let mut ok = n; let mut ng = 0; while ok.abs_diff(ng) > 1 { let mid = (ok + ng) / 2; let progress = calc_progress(0, mid); if progress.0 >= h || progress.1 >= w { ok = mid; } else { ng = mid; } } return ok % n; }; for &(h, w, p) in &hwp { println!("{}", solve(h, w, p)); } }