문제

ビ太郎は，誕生日プレゼントとしてJOI マシンをもらった．JOI マシンは，1 個のボール，$N$ 個のライトタイル，$M$ 個のボタンからなる．ライトタイルにはそれぞれ $1$ から $N$ までの番号が付けられており，電源を入れると，ライトタイル $i$ ($1 \le i \le N$) は色 $C_i$ (青(B)，赤(R) のいずれか) で光るようになっている．また，ボタンにはそれぞれ $1$ から $M$ までの番号が付けられており，ボタン $j$ ($1 \le j \le 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 \le k \le Q$) の実験は，JOI マシンの電源を入れた後，ボタン $L_k, L_k + 1, \ldots, R_k$ をこの順に押すというものである．ただし，ボールが取り除かれるまでは，次のボタンを押さずに待つものとする．

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

입력

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

N M
C_1 C_2 ... C_N
A_1 A_2 ... A_M
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

출력

標準出力に $Q$ 行出力せよ．$k$ 行目 ($1 \le k \le Q$) には，$k$ 回目の実験が終わった後における，色が赤であるようなライトタイルの個数を出力せよ．

예제 입력 1

5 1
RBRRB
4
1
1 1

예제 출력 1

1

예제 입력 2

5 3
RBRBR
1 3 4
2
2 3
1 3

예제 출력 2

5
0

예제 입력 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

예제 출력 3

2

예제 입력 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

예제 입력 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

예제 입력 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

제한

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

서브태스크

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