题目描述

译自 JOI 2023 Final T5「現代的な機械 / Modern Machine」

Bitaro 生日这天收到了一个 JOI 机作为生日礼物。JOI 机由一个球，$N$ 条光带和 $M$ 个按钮组成。光带从 $1$ 到 $N$ 编号。当 Bitaro 打开开关时，光带 $i\ (1\le i\le N)$ 会发出颜色 $C_i$ 的光（蓝光 ($\texttt{B}$) 或红光 ($\texttt{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,\ldots R_k$ 的顺序按下这些开关。在 Bitaro 按下一个开关后，他将等到球被移除后再按下下一个开关。

给定 JOI 机和实验的情况，写一个程序计算对于每个实验，当实验结束后红色的光带有多少。

注：每次实验之间互相独立。

输入格式

第一行两个整数 $N,M$。

第二行一个长度为 $N$ 的字符串 $C$，字符串中仅包含字符 $\texttt{R}$ 和 $\texttt{B}$。

第三行 $M$ 个整数 $A_j$。

第四行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $L_k,R_k$。

输出格式

输出 $Q$ 行，第 $k\ (1\le k\le Q)$ 行输出一个整数，表示当第 $k$ 个实验结束后红色的光带有多少。

5 1
RBRRB
4
1
1 1

1

第一个实验按如下进行。

1. Bitaro 按下按钮 $1$，然后球被放在光带 $4$ 上。
2. 光带 $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$ 的限制。

5 3
RBRBR
1 3 4
2
2 3
1 3

5
0

对于第一个实验，在结束后光带 $1,2,3,4,5$ 都是红色的，所以输出 $5$。

对于第二个实验，在结束后没有光带是红色的，所以输出 $0$。

这组样例满足子任务 $3,6,7$ 的限制。

10 3
BBRRBRBRRB
2 10 5
1
1 3

2

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

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

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

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

这组样例满足子任务 $3,5,6,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

这组样例满足子任务 $6,7$ 的限制。

数据范围与提示

对于全部数据，满足

• $3\le N\le 1.2\times 10^5$
• $1\le M\le 1.2\times 10^5$
• $C_i\ (1\le i\le N)$ 不是 $\texttt{B}$ 就是 $\texttt{R}$
• $1\le A_j\le N\ (1\le j\le M)$
• $1\le Q\le 1.2\times 10^5$
• $1\le L_k\le R_k\le M\ (1\le k\le Q)$

详细子任务附加限制及分值如下表。