27540번 - Modern Machine 서브태스크다국어

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

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

Bitaro is interested in JOI machine. He plans to perform $Q$ experiments. In the $k$-th experiment ($1 ≤ k ≤ Q$), after Bitaro turns the power on, Bitaro pushes Buttons $L_k, L_{k + 1}, \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.

$N$ $M$

$C_1C_2 \cdots C_N$

$A_1$ $A_2$ $\cdots$ $A_M$

$Q$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_Q$ $R_Q$

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

• $3 ≤ N ≤ 120\,000$.
• $1 ≤ M ≤ 120\,000$.
• $C_i$ ($1 ≤ i ≤ N$) is either B or R.
• $1 ≤ A_j ≤ N$ ($1 ≤ j ≤ M$).
• $1 ≤ Q ≤ 120\,000$.
• $1 ≤ L_k ≤ R_k ≤ M$ ($1 ≤ k ≤ Q$).
• $N$, $M$, $A_j$, $Q$, $L_k$, $R_k$ are integers.