Modern Machine

Bitaro was given a JOI machine as a birthday present. The 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 \le i \le N$) emits light of color $C_i$ (blue B or red R). The buttons are numbered from $1$ to $M$. When Bitaro pushes button $j$ ($1 \le j \le M$), the following happens.

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 steps repeat until the ball is removed.
   • Let $p$ be the index of the light tile where the ball currently is.
   • If light tile $p$ is blue, light tile $p$ becomes red. Then, 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. Then, if $p = N$, the ball is removed. Otherwise, the ball moves to light tile $p + 1$.

Bitaro runs $Q$ experiments. In the $k$-th experiment ($1 \le k \le Q$), Bitaro turns the power on, then pushes buttons $L_k, L_{k+1}, \dots, R_k$ in this order. After he pushes a button, he waits until the ball is removed before pushing the next one. For each experiment, find the number of light tiles that are red when the experiment finishes.

The input is given in the following format.

$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$

Print $Q$ lines. On the $k$-th line, print the number of light tiles that are red when the $k$-th experiment finishes.

• $3 \le N \le 120\,000$.
• $1 \le M \le 120\,000$.
• $C_i$ ($1 \le i \le N$) is either B or 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$ are integers.