Problem Description

Bitaro receives 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 on the power, Light tile $i$ ($1 \leq i \leq N$) emits light of color $C_i$ (blue ($\texttt B$) or red ($\texttt R$)). The buttons are numbered from $1$ to $M$. If Bitaro presses Button $j$ ($1 \leq j \leq M$), the following events occur:
1. The ball is placed on Light tile $A_j$.
2. Light tile $A_j$ turns 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$ turns 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$ turns blue. After that, if $p = N$, the ball is removed. Otherwise, the ball moves to Light tile $p + 1$.

Bitaro plans to conduct $Q$ experiments. In the $k$-th experiment ($1 \leq k \leq Q$), after turning on the power, Bitaro presses Buttons $L_k, L_{k + 1}, \dots, R_k$ in this order. After pressing a button, he waits until the ball is removed before pressing the next button.

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

Input Format

Read the following data from the standard input:

$N$ $M$
$C_1\ C_2 \dots C_N$
$A_1\ A_2 \dots A_M$
$Q$
$L_1\ R_1$
$L_2\ R_2$
$\dots$
$L_Q\ R_Q$

Output Format

Write $Q$ lines to the standard output. In the $k$-th line ($1 \leq k \leq Q$), output the number of light tiles that are red when the $k$-th experiment finishes.

Sample Input and Output

Input Sample #1

5 1
RBRRB
4
1
1 1

Output Sample #1

1

Input Sample #2

5 3
RBRBR
1 3 4
2
2 3
1 3

Output Sample #2

5
0

Input Sample #3

10 3
BBRRBRBRRB
2 10 5
1
1 3

Output Sample #3

2

Input Sample #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

Output Sample #4

4
8
10
0
9

Input Sample #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

Output Sample #5

2
6
0
10
7

Input Sample #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

Output Sample #6

21
15
15
4
17
16
14
20
12
23

Notes/Hints

[Sample Explanation #1]

The first experiment proceeds as follows:
1. Bitaro presses Button 1, and the ball is placed on Light tile 4.
2. Light tile 4 turns red. Since the original color of Light tile 4 is red, its color 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 turns blue, and the ball moves to Light tile 5.
(2) Since the current color of Light tile 5 is blue, Light tile 5 turns red, and the ball moves to Light tile 4.
(3) Since the current color of Light tile 4 is blue, Light tile 4 turns red, and the ball moves to Light tile 3.
(4) Since the current color of Light tile 3 is red, Light tile 3 turns blue, and the ball moves to Light tile 4.
(5) Since the current color of Light tile 4 is red, Light tile 4 turns blue, and the ball moves to Light tile 5.
(6) Since the current color of Light tile 5 is red, Light tile 5 turns 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 satisfies the constraints of Subtasks 1, 2, 3, 6, 7.

[Sample Explanation #2]

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 satisfies the constraints of Subtasks 3, 6, 7.

[Sample Explanation #3]

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

[Sample Explanation #4]

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

[Sample Explanation #5]

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

[Sample Explanation #6]

This sample satisfies the constraints of Subtasks 6, 7.

[Data Size]

For all test cases, the following constraints are guaranteed:
- $3 \leq N \leq 1.2 \times 10^5$;
- $1 \leq M \leq 1.2 \times 10^5$;
- $C_i \in \{\texttt{B},\texttt{R}\}$;
- $1 \leq A_j \leq N$;
- $1 \leq Q \leq 1.2 \times 10^5$;
- $1 \leq L_k \leq R_k \leq M$;
- $N, M, A_j, Q, L_k, R_k$ are integers.

[Subtasks]

This problem is bundled-tasked.

1. (3 points) $N, M \leq 300$, $Q = 1$.
2. (12 points) $N, M \leq 7000$, $Q = 1$.
3. (10 points) $Q \leq 5$.
4. (11 points) $N = 10$, $C_i = \texttt R$.
5. (26 points) There exists an integer $t \in [0, N]$ such that for $1 \leq i \leq t$, $C_i = \texttt R$; and for $t < i \leq N$, $C_i = \texttt B$.
6. (17 points) $A_j \leq 20$ or $A_j > N - 20$.
7. (21 points) No special constraints.

见题面 Input 部分

见题面 Output 部分