Bitaro 收到了一台 JOI 机器作为生日礼物。JOI 机器由一个球、 $N$ 个灯块和 $M$ 个按钮组成。灯块编号为 $1$ 到 $N$。当 Bitaro 接通电源时，灯块 $i$ ($1 \le i \le N$) 会发出颜色为 $C_i$（蓝色 (B) 或红色 (R)）的光。按钮编号为 $1$ 到 $M$。如果 Bitaro 按下按钮 $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$。

Bitaro 对这台 JOI 机器很感兴趣。他计划进行 $Q$ 次实验。在第 $k$ 次实验 ($1 \le k \le Q$) 中，Bitaro 接通电源后，依次按下按钮 $L_k, L_k + 1, \dots, R_k$。在 Bitaro 按下一个按钮后，他不会按下下一个按钮，而是等待球被移除。

给定 JOI 机器的信息和实验内容，请编写一个程序，计算每次实验结束时，颜色为红色的灯块数量。

输入格式

从标准输入读取以下数据：

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

输出格式

向标准输出写入 $Q$ 行。第 $k$ 行 ($1 \le k \le Q$) 应包含第 $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$ 均为整数

子任务

1. (3 分) $N \le 300, M \le 300, Q = 1$
2. (12 分) $N \le 7\,000, M \le 7\,000, Q = 1$
3. (10 分) $Q \le 5$
4. (11 分) $N = 10$, 且 $C_i$ 为 R ($1 \le i \le N$)
5. (26 分) 存在整数 $t$ ($0 \le t \le N$)，使得对于所有 $i \le t$，$C_i$ 为 R，且对于所有 $i > t$，$C_i$ 为 B
6. (17 分) $A_j \le 20$ 或 $A_j > N - 20$ ($1 \le j \le M$)
7. (21 分) 无附加限制

样例

样例输入 1

5 1
RBRRB
4
1
1 1

样例输出 1

1

样例输入 2

5 3
RBRBR
1 3 4
2
2 3
1 3

样例输出 2

5
0

样例输入 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

样例输出 3

2

样例输入 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

样例输入 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

样例输入 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