問題文

ビ太郎は，誕生日プレゼントとして JOI マシンをもらった． JOI マシンは，1 個の ボール，N 個の ライトタイル，M 個の ボタン からなる． ライトタイルにはそれぞれ 1 から N までの番号が付けられており， 電源を入れると，ライトタイル i (1 \leqq i \leqq N) は色 C_i (青 (B)，赤 (R) のいずれか) で光るようになっている． また，ボタンにはそれぞれ 1 から M までの番号が付けられており， ボタン j (1 \leqq j \leqq M) を押すと，次のようなことが起こる．

1. ライトタイル A_j の上にボールが置かれる．
2. ライトタイル A_j の色が (元の色にかかわらず) 赤になる．

3. ボールが取り除かれるまで，以下のことが繰り返し行われる．

   今，ボールが置かれているライトタイルの番号を p とする．

   ライトタイル p の色が青の場合

   ライトタイル p の色が赤に変わる．その後，もし p=1 の場合はボールが取り除かれ，そうでない場合はボールがライトタイル p-1 の上に移動する．

   ライトタイル p の色が赤の場合

   ライトタイル p の色が青に変わる．その後，もし p=N の場合はボールが取り除かれ，そうでない場合はボールがライトタイル p+1 の上に移動する．

JOI マシンに興味を持ったビ太郎は，Q 回の実験を計画している． k 回目 (1 \leqq k \leqq Q) の実験は，JOI マシンの電源を入れた後，ボタン L_k, L_k+1, \ldots, R_k をこの順に押すというものである． ただし，ボールが取り除かれるまでは，次のボタンを押さずに待つものとする．

JOI マシンの情報および実験の情報が与えられるので， それぞれの実験について，実験が終わった後における，色が赤であるようなライトタイルの個数を求めるプログラムを作成せよ．

制約

• 3 \leqq N \leqq 120\,000．
• 1 \leqq M \leqq 120\,000．
• C_i (1 \leqq i \leqq N) は B または R である．
• 1 \leqq A_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq Q \leqq 120\,000．
• 1 \leqq L_k \leqq R_k \leqq M (1 \leqq k \leqq Q)．
• N, M, A_j, Q, L_k, R_k は整数である．

小課題

• (3 点) N \leqq 300，M \leqq 300，Q = 1．
• (12 点) N \leqq 7\,000，M \leqq 7\,000，Q = 1．
• (10 点) Q \leqq 5．
• (11 点) N = 10，C_i は R である (1 \leqq i \leqq N)．
• (26 点) i \leqq t ならば C_i が R であり，i > t であれば C_i が B であるような整数 t (0 \leqq t \leqq N) が存在する．
• (17 点) A_j \leqq 20 または A_j > N - 20 (1 \leqq j \leqq M)．
• (21 点) 追加の制約はない．

入力例 1

5 1
RBRRB
4
1
1 1

出力例 1

1

1 回目の実験は次のように進行する．

1. ボタン 1 が押され，ボールがライトタイル 4 の上に置かれる．
2. ライトタイル 4 の色が赤になる．ただし，元からライトタイル 4 の色が赤なので，ライトタイル 4 の色は変わらない．
3. その後，次のことが起こる．
   1. 現在のライトタイル 4 の色は赤なので，ライトタイル 4 の色が青に変わり，ボールがライトタイル 5 の上に移動する．
   2. 現在のライトタイル 5 の色は青なので，ライトタイル 5 の色が赤に変わり，ボールがライトタイル 4 の上に移動する．
   3. 現在のライトタイル 4 の色は青なので，ライトタイル 4 の色が赤に変わり，ボールがライトタイル 3 の上に移動する．
   4. 現在のライトタイル 3 の色は赤なので，ライトタイル 3 の色が青に変わり，ボールがライトタイル 4 の上に移動する．
   5. 現在のライトタイル 4 の色は赤なので，ライトタイル 4 の色が青に変わり，ボールがライトタイル 5 の上に移動する．
   6. 現在のライトタイル 5 の色は赤なので，ライトタイル 5 の色が青に変わり，ボールが取り除かれる．

実験が終わった時点で，色が赤であるようなライトタイルはライトタイル 1 の 1 つのみであるため，1 を出力する．

この入力例は小課題 1, 2, 3, 6, 7 の制約を満たす．

入力例 2

5 3
RBRBR
1 3 4
2
2 3
1 3

出力例 2

5
0

1 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルはライトタイル 1, 2, 3, 4, 5 の 5 つであるため，5 を出力する．

2 回目の実験については，実験が終わった時点で，色が赤であるようなライトタイルは存在しないため，0 を出力する．

この入力例は小課題 3, 6, 7 の制約を満たす．

入力例 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

出力例 3

2

この入力例は小課題 1, 2, 3, 6, 7 の制約を満たす．

入力例 4

10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10

出力例 4

4
8
10
0
9

この入力例は小課題 3, 4, 5, 6, 7 の制約を満たす．

入力例 5

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

出力例 5

2
6
0
10
7

この入力例は小課題 3, 5, 6, 7 の制約を満たす．

入力例 6

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

出力例 6

21
15
15
4
17
16
14
20
12
23

この入力例は小課題 6, 7 の制約を満たす．