题目描述

K 主席计划在接下来 $N$ 天内举办一系列会议，每天都会举办恰好一场会议，且会议将在三个场馆之一举行：主场馆 A 或两个副场馆 B 和 C 中的一个。

每场会议的场馆信息由字符串 $S$ 给出，该字符串由 $\texttt{A}$、$\texttt{B}$、$\texttt{C}$ 和 $\texttt{?}$ 组成。对于第 $i$ 天（$1 \leq i \leq N$），如果 $S$ 的第 $i$ 个字符是 $\texttt{A}$，则会议在场馆 A 举行；如果是 $\texttt{B}$，则在场馆 B 举行；如果是 $\texttt{C}$，则在场馆 C 举行；如果是 $\texttt{?}$，则表示第 $i$ 天的场馆尚未决定。

由于第一天和第 $N$ 天的会议预计会有大量参与者，因此已确定这两天必须使用场馆 A。

现在，K 主席需要为每个未决定的会议分配场馆（每个 $\texttt{?}$ 处可以选择 A、B 或 C）。此外，为了最小化场馆间移动的负担，他希望最小化满足以下条件的索引 $j$（$1 \leq j \leq N-1$）的数量：第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同。

现在需要考虑 $Q$ 个分配场景。对于第 $k$ 个场景（$1 \leq k \leq Q$）及其对应的问题描述如下：

• K 主席必须将 $X_k$ 个未决定的会议分配到场馆 A，$Y_k$ 个分配到场馆 B，$Z_k$ 个分配到场馆 C。
• 请确定在此条件下，满足「第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同」的最小可能索引 $j$ 的数量。

给定场馆信息和需要考量的场景，请编写程序回答这些问题。

输入格式

$N$
$S$
$Q$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_Q$ $Y_Q$ $Z_Q$

输出格式

输出 $Q$ 行。

在第 $k$ 行（$1 \leq k \leq Q$）中，输出在 K 主席将 $X_k$ 个未决定会议分配到 A，$Y_k$ 个分配到 B，$Z_k$ 个分配到 C 的条件下，满足「第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同」的最小可能索引 $j$ 的数量。

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

3
4
4

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

4
4
2
2

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17

提示

样例解释

样例解释 $1$

在第一个场景中，K 主席需要将 $5$ 个未决定会议中的 $1$ 个分配到场馆 A，$3$ 个分配到 B，$1$ 个分配到 C。例如，一种可能的分配结果会生成场馆信息字符串 $\texttt{ABBBBCCAA}$。此时，满足"第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同"的索引 $j$ 是 $1$、$5$、$7$，共 $3$ 个。由于无法将这个数量减少到 $2$ 或更少，因此第一行的正确输出是 $3$。

在第二个场景中，K 主席需要将 $5$ 个未决定会议中的 $4$ 个分配到 A，$1$ 个分配到 B。例如，一种可能的分配结果会生成字符串 $\texttt{AAABBACAA}$。此时，满足条件的索引 $j$ 是 $3$、$5$、$6$、$7$，共 $4$ 个。因此第二行的正确输出是 $4$。

在第三个场景中，K 主席需要将所有 $5$ 个未决定会议分配到 C。满足条件的索引 $j$ 是 $1$、$3$、$4$、$8$，共 $4$ 个。因此第三行的正确输出是 $4$。

该样例满足子任务 $1\sim 5,8$ 的限制。

样例解释 $2$

该样例满足所有子任务的限制。

样例解释 $3$

该样例满足子任务 $1,2,4,8$ 的限制。

数据范围

• $2 \leq N \leq 300\,000$；
• $S$ 是长度为 $N$ 且由 $\texttt{A}$、$\texttt{B}$、$\texttt{C}$ 和 $\texttt{?}$ 组成的字符串；
• $S$ 的首字符和末字符均为 $\texttt{A}$；
• $1 \leq Q \leq 200\,000$；
• $0 \leq X_k$（$1 \leq k \leq Q$）；
• $0 \leq Y_k$（$1 \leq k \leq Q$）；
• $0 \leq Z_k$（$1 \leq k \leq Q$）；
• $X_k + Y_k + Z_k$ 等于 $S$ 中 $\texttt{?}$ 的数量（$1 \leq k \leq Q$）；
• $N$、$Q$、$X_k$、$Y_k$、$Z_k$ 均为整数。

子任务

• $\text{Subtask 1 (4 pts)}$：$N \leq 50$ 且 $S$ 中 $\texttt{?}$ 的数量不超过 $13$；
• $\text{Subtask 2 (7 pts)}$：$N \leq 500$；
• $\text{Subtask 3 (13 pts)}$：$N \leq 5\,000$，$Q \leq 10$；
• $\text{Subtask 4 (18 pts)}$：$N \leq 5\,000$；
• $\text{Subtask 5 (12 pts)}$：$Q \leq 10$；
• $\text{Subtask 6 (8 pts)}$：$S$ 不含 $\texttt{C}$ 且所有 $Z_k = 0$（$1 \leq k \leq Q$）；
• $\text{Subtask 7 (13 pts)}$：所有 $Z_k = 0$（$1 \leq k \leq Q$）；
• $\text{Subtask 8 (25 pts)}$：无额外限制。