Description

Bitaro 收到了一个 JOI 机器作为生日礼物。

JOI 机器由一个球、$N$ 个灯光瓷砖和 $M$ 个按钮组成。灯光瓷砖从 $1$ 到 $N$ 编号。当 Bitaro 打开电源时，灯光瓷砖 $i$ ($1 \leq i \leq N$) 会发出颜色为 $C_i$（蓝色（$\texttt B$）或红色（$\texttt R$））的光。按钮从 $1$ 到 $M$ 编号。

如果 Bitaro 按下按钮 $j$ ($1 \leq j \leq 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 \leq k \leq Q$），在 Bitaro 打开电源后，Bitaro 按顺序按下按钮 $L_k, L_{k} + 1, \dots , R_k$。在 Bitaro 按下一个按钮后，他不会按下下一个按钮，并等待球被移除。

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

Input Format

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

$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

向标准输出写入 $Q$ 行。在第 $k$ 行（$1 \leq k \leq Q$），输出应包含第 $k$ 次实验结束时颜色为红色的灯光瓷砖的数量。

5 1
RBRRB
4
1
1 1

1

5 3
RBRBR
1 3 4
2
2 3
1 3

5
0

10 3
BBRRBRBRRB
2 10 5
1
1 3

2

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
8
10
0
9

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

2
6
0
10
7

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

21
15
15
4
17
16
14
20
12
23

Hint

【样例解释 #1】

第一次实验如下进行。

1. Bitaro 按下按钮 1，球被放置在灯光瓷砖 4 上。
2. 灯光瓷砖 4 变为红色。由于灯光瓷砖 4 的原始颜色是红色，灯光瓷砖 4 的颜色没有改变。
3. 之后，执行以下操作。
   （1）由于灯光瓷砖 4 的当前颜色是红色，灯光瓷砖 4 变为蓝色，球移动到灯光瓷砖 5。
   （2）由于灯光瓷砖 5 的当前颜色是蓝色，灯光瓷砖 5 变为红色，球移动到灯光瓷砖 4。
   （3）由于灯光瓷砖 4 的当前颜色是蓝色，灯光瓷砖 4 变为红色，球移动到灯光瓷砖 3。
   （4）由于灯光瓷砖 3 的当前颜色是红色，灯光瓷砖 3 变为蓝色，球移动到灯光瓷砖 4。
   （5）由于灯光瓷砖 4 的当前颜色是红色，灯光瓷砖 4 的颜色变为蓝色，球移动到灯光瓷砖 5。
   （6）由于灯光瓷砖 5 的当前颜色是红色，灯光瓷砖 5 的颜色变为蓝色，球被移除。

实验结束后，灯光瓷砖 1 是唯一一个当前颜色为红色的灯光瓷砖。因此，输出 1。

本样例满足子任务 1,2,3,6,7 的限制。

【样例解释 #2】

对于第一次实验，灯光瓷砖 1, 2, 3, 4, 5 是实验结束后当前颜色为红色的灯光瓷砖。由于有五个这样的灯光瓷砖，输出 5。

对于第二次实验，没有灯光瓷砖在实验结束后颜色为红色。因此，输出 0。

本样例满足子任务 3,6,7 的限制。

【样例解释 #3】

本样例满足子任务 1,2,3,6,7 的限制。

【样例解释 #4】

本样例满足子任务 3,4,5,6,7 的限制。

【样例解释 #5】

本样例满足子任务 3,5,6,7 的限制。

【样例解释 #6】

本样例满足子任务 6,7 的限制。

【数据规模】

对全部的测试点，保证：

• $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$ 均为整数。

【子任务】

本题采用捆绑测试。

1. (3 分) $N,M \leq 300$，$Q = 1$。
2. (12 分) $N, M \leq 7000$，$Q = 1$。
3. (10 分) $Q \leq 5$。
4. (11 分) $N = 10$，$C_i = \texttt R$。
5. (26 分) 存在一个整数 $t \in [0, N]$，满足对 $1 \leq i \leq t$，$C_i = \texttt R$；且对 $t < i \leq N$，$C_i = \texttt B$。
6. (17 分) $A_j \leq 20$ 或 $A_j > N - 20$。
7. (21 分) 无特殊约定。

题面翻译由 ChatGPT-4o 提供。