题目描述

译自 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

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

数据范围与提示

对于全部数据，满足

• $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)$

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

子任务编号	附加限制	分值
$1$	$N\le 300,M\le 300,Q\le 1$	$3$
$2$	$N\le 7\ 000,M\le 7\ 000,Q=1$	$12$
$3$	$Q\le 5$	$10$
$4$	$N=10$ 且 $C_i\ (1\le i\le N)$ 是 $\texttt{R}$	$11$
$5$	存在一个整数 $t\ (0\le t\le N)$，使得对于每个 $i\le t$ 都有 $C_i$ 是 $\texttt{R}$，对于每个 $i>t$ 都有 $C_i$ 是 $\texttt{B}$	$26$
$6$	$A_j\le 20$ 或 $A_j>N-20\ (1\le j\le M)$	$17$
$7$	无附加限制	$21$