問題文

D，R のみからなる長さ $N$ の文字列 $S = S_0 S_1 \cdots S_{N-1}$ が与えられます（添字が $0$ 始まりであることに注意してください）．

二次元グリッド上を移動する手続き $F(h, w, p)$ を以下のように定めます：

1. 位置を $(0, 0)$，カウンタの値を $p$ で初期化する．
2. 現在の位置が $(x, y)$，カウンタの値が $i$ であるとき，
   • $x = h$ かつ $y = w$ である場合，手続きを終了する．
   • そうでなく $x = h$ である場合，位置を $(x, y + 1)$ に更新して 2. に戻る．
   • そうでなく $y = w$ である場合，位置を $(x + 1, y)$ に更新して 2. に戻る．
   • そうでない場合，$\bmod$ を剰余を表す二項演算子として，
     • $S_i=$ D ならば位置を $(x + 1, y)$ に，カウンタを $(i + 1) \bmod N$ にそれぞれ更新して 2. に戻る．
     • $S_i=$ R ならば位置を $(x, y + 1)$ に，カウンタを $(i + 1) \bmod N$ にそれぞれ更新して 2. に戻る．

$Q$ 個のクエリが与えられます．$i$ 番目のクエリは整数の組 $(H_i, W_i, P_i)$ で表されるので，手続き $F(H_i, W_i, P_i)$ を終えた後のカウンタの値を求めてください．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq H_i, W_i \leq 10^9$
• $0 \leq P_i < N$
• $S$ は D，R のみからなる長さ $N$ の文字列
• 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられます．

$N \ Q$
$S$
$H_1 \ W_1 \ P_1$
$\vdots$
$H_Q \ W_Q \ P_Q$

出力

$Q$ 行出力してください．$i$ 行目には手続き $F(H_i, W_i, P_i)$ を終えた後のカウンタの値を出力してください．
最後に改行してください．

サンプル

4 3
RDDR
3 2 1
1 7 0
4 1 3

1
2
0