K 理事长计划运营 $N$ 天的会议。每天（第 $1$ 天至第 $N$ 天）将举办一场会议，每场会议会使用主会场 A 或辅会场 B、C 中的一个。

每场会议使用的会场信息以只包含 A、B、C、? 的字符串 $S$ 给出。对于第 $i$ 天（$1 \leq i \leq N$），若 $S$ 的第 $i$ 个字符为 A，则第 $i$ 天的会议在会场 A 举行，若为 B 则在会场 B，若为 C 则在会场 C，若为 ? 则尚未确定。不过，第 $1$ 天和第 $N$ 天的会议因有更多人参加，已确定在会场 A 举办。

接下来，K 理事长需要为尚未确定会场的会议分配会场，每个未定会议都要分配到会场 A、B、C 的其中一个。为了减少与会人员的移动负担，希望使得满足 $j$ 天和 $j+1$ 天会议的会场不同的 $j$ 的个数（$1\leq j\leq N-1$）最小。

关于如何分配未定会议的会场，将给出 $Q$ 个不同的分配场景，需要分别计算上面所述的 $j$ 的最小个数。第 $k$ 个（$1\leq k\leq Q$）场景定义如下：

• 对于尚未确定会场的会议，分配 $X_k$ 个到会场 A，$Y_k$ 个到会场 B，$Z_k$ 个到会场 C。在这种分配下，求出 $j$ 天和 $j+1$ 天会议的会场不同的 $j$ 的个数的最小值。

给定会场信息和 $Q$ 个分配场景，请编写程序回答每个场景下的最小值。

---

输入以如下格式从标准输入给出：

$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$ 的最小个数。

小子任务

1.（4分）$N \leq 50$，$S$ 中出现的 ? 不超过 $13$ 个。
2.（7分）$N \leq 500$。
3.（13分）$N \leq 5\,000$，$Q \leq 10$。
4.（18分）$N \leq 5\,000$。
5.（12分）$Q \leq 10$。
6.（8分）$S$ 中不包含 C，且所有 $Z_k = 0$（$1\leq k \leq Q$）。
7.（13分）所有 $Z_k = 0$（$1\leq k \leq Q$）。
8.（25分）无附加限制。

---

样例说明 1

第 $1$ 个场景：5 个未定会议中，分配 1 个到 A，3 个到 B，1 个到 C。例如，最终会场分配为 ABBBBCCAA，此时满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $1,5,7$，共 $3$ 个。无法做到不超过 $2$ 个，因此第 1 行输出 3。

第 $2$ 个场景：5 个未定会议中，分配 4 个到 A，1 个到 B。例如，最终会场分配为 AAABBACAA，此时满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $3,5,6,7$，共 $4$ 个。无法做到不超过 $3$ 个，因此第 2 行输出 4。

第 $3$ 个场景：5 个未定会议全部分配到 C，满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $1,3,4,8$，共 $4$ 个，因此第 3 行输出 4。

本输入示例满足小子任务 1,2,3,4,5,8 的限制。

---

样例说明 2

本输入示例满足所有小子任务的限制要求。

---

样例说明 3

本输入示例满足小子任务 1,2,4,8 的限制。

数据范围与约定

• $2 \leq N \leq 300\,000$。
• $S$ 是由 A、B、C、? 组成的长为 $N$ 的字符串。
• $S$ 的第 $1$ 个和第 $N$ 个字符为 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$ 中 ? 的数量（$1\leq k \leq Q$）。
• $N, Q, X_k, Y_k, Z_k$ 均为整数（$1\leq k \leq Q$）。

由 ChatGPT 5 翻译