현대적인 기계

비타로는 생일 선물로 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$로 옮긴다.

비타로는 $Q$번의 실험을 한다. $k$번째 실험($1 \le k \le Q$)에서 비타로는 전원을 켠 뒤 버튼 $L_k, L_{k+1}, \dots, R_k$를 이 순서대로 누른다. 버튼을 누른 뒤에는 공이 제거될 때까지 기다렸다가 다음 버튼을 누른다. 각 실험이 끝났을 때 빨간색인 조명 타일의 개수를 구하라.

입력은 표준 입력에서 다음 형식으로 주어진다.

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

$Q$개의 줄을 표준 출력에 출력한다. $k$번째 줄에는 $k$번째 실험이 끝났을 때 빨간색인 조명 타일의 개수를 출력한다.

• $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$는 정수이다.