시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB54448.333%

문제

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.

서브태스크

번호배점제한
13

$N ≤ 300$, $M ≤ 300$, $Q = 1$.

212

$N ≤ 7\,000$, $M ≤ 7\,000$, $Q = 1$.

310

$Q ≤ 5$.

411

$N = 10$, and $C_i$ is R ($1 ≤ i ≤ N$).

526

There exists an integer $t$ ($0 ≤ t ≤ N$) such that $C_i$ is R for every $i ≤ t$, and $C_i$ is B for every $i > t$.

617

$A_j ≤ 20$ or $A_j > N - 20$ ($1 ≤ j ≤ M$).

721

No additional constraints.

예제 입력 1

5 1
RBRRB
4
1
1 1

예제 출력 1

1

The first experiment proceeds as follows.

  1. Bitaro pushes Button $1$, and ball is placed on Light tile $4$.
  2. Light tile $4$ becomes red. Since the original color of Light tile $4$ is red, the color of Light tile $4$ does not change.
  3. After that, the following operations are performed.
    1. Since the current color of Light tile $4$ is red, Light tile $4$ becomes blue, and the ball moves to Light tile $5$.
    2. Since the current color of Light tile $5$ is blue, Light tile $5$ becomes red, and the ball moves to Light tile $4$.
    3. Since the current color of Light tile $4$ is blue, Light tile $4$ becomes red, and the ball moves to Light tile $3$.
    4. Since the current color of Light tile $3$ is red, Light tile $3$ becomes blue, and the ball moves to Light tile $4$.
    5. Since the current color of Light tile $4$ is red, the color of Light tile $4$ becomes blue, and the ball moves to Light tile $5$.
    6. Since the current color of Light tile $5$ is red, the color of Light tile $5$ becomes blue, and the ball is removed.

After the experiment, Light tile $1$ is the only light tile whose current color is red. Therefore, output $1$.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6, 7.

예제 입력 2

5 3
RBRBR
1 3 4
2
2 3
1 3

예제 출력 2

5
0

For the first experiment, Light tiles $1$, $2$, $3$, $4$, $5$ are the light tiles whose current colors are red after the experiment. Since there are five such light tiles, output $5$.

For the second experiment, there is no light tile whose current color is red after the experiment. Therefore, output $0$.

This sample input satisfies the constraints of Subtasks 3, 6, 7.

예제 입력 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

예제 출력 3

2

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6, 7.

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

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6, 7.

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

This sample input satisfies the constraints of Subtasks 3, 5, 6, 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

This sample input satisfies the constraints of Subtasks 6, 7.

채점 및 기타 정보

  • 예제는 채점하지 않는다.