Modern Machine

문제

Bitaro is given JOI machine as a birthday present. JOI machine consists of one ball, $NN$ light tiles, and $MM$ buttons. The light tiles are numbered from $11$ to $NN$. When Bitaro turns the power on, Light tile $ii$ (1 ≤ i ≤ N) emit light of color $C_{i}C\_i$ (blue (B) or red (R)). The buttons are numbered from $11$ to $MM$. If Bitaro pushes Button $jj$ (1 ≤ j ≤ M), the following happen.

1. The ball is placed on Light tile $A_{j}A\_j$.
2. Light tile $A_{j}A\_j$ becomes red (regardless of its original color).
3. The following operations are performed until the ball is removed.
   • Let $pp$ be the index of the light tile where the ball is currently placed.
   • If Light tile $pp$ is blue,
     • Light tile $pp$ becomes red. After that, if $p=1p\; =\; 1$, the ball is removed. Otherwise, the ball moves to Light tile $p-1p\; -\; 1$.
   • If Light tile $pp$ is red,
     • Light tile $pp$ becomes blue. After that, if $p=Np\; =\; N$, the ball is removed. Otherwise, the ball moves to Light tile $p+1p\; +\; 1$.

Bitaro is interested in JOI machine. He plans to perform $QQ$ experiments. In the $kk$-th experiment (1 ≤ k ≤ Q), after Bitaro turns the power on, Bitaro pushes Buttons $L_k,L_{k+1},\dots ,R_{k}L\_k,\; L\_\{k\; +\; 1\},\; \backslash dots\; ,\; R\_k$ in this order. After Bitaro pushes a button, he will not push the next button and wait until the ball is removed.

Given information of JOI machine and the experiments, write a program which calculates, for each experiment, the number of light tiles whose colors are red when the experiment finishes.

입력

Read the following data from the standard input.

$NN$ $MM$

$C_1{C}_2\cdots C_{N}C\_1C\_2\; \backslash cdots\; C\_N$

$A_{1}A\_1$ $A_{2}A\_2$ $\cdots \backslash cdots$ $A_{M}A\_M$

$QQ$

$L_{1}L\_1$ $R_{1}R\_1$

$L_{2}L\_2$ $R_{2}R\_2$

$\mathrm{⋮}\backslash vdots$

$L_{Q}L\_Q$ $R_{Q}R\_Q$

출력

Write $QQ$ lines to the standard output. In the $kk$-th line (1 ≤ k ≤ Q), the output should contain the number of light tiles whose colors are red when the $kk$-th experiment finishes.

5 1
RBRRB
4
1
1 1

1

5 3
RBRBR
1 3 4
2
2 3
1 3

5
0

10 3
BBRRBRBRRB
2 10 5
1
1 3

2

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
8
10
0
9

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

2
6
0
10
7

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

21
15
15
4
17
16
14
20
12
23