AT_utpc2025_m Max Conference

> 解过 [Conference](https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference.pdf) 的人，也许很自然地就能想到这个问题。 给定一个长度为 $N$ 的字符串 $S$，其中 $S$ 的每个字符都是 `A`、`B`、`C`、`?` 之一，且特别地，$S$ 的第 $1$ 个和第 $N$ 个字符都是 `A`。 我们将使每个字符都是 `A`、`B` 或 `C` 的字符串的**分数**定义为：$i$ 满足 $1 \leq i \leq N-1$，且第 $i$ 个字符与第 $i+1$ 个字符不同的 $i$ 的个数。 请你回答 $Q$ 个询问。第 $i$ 个询问如下： > 给定非负整数 $X_i, Y_i, Z_i$。其中 $X_i + Y_i + Z_i$ 等于 $S$ 中 `?` 的总个数。将 $S$ 中的 `?` 全部替换为恰好 $X_i$ 个 `A`、$Y_i$ 个 `B`、$Z_i$ 个 `C` 后，所能获得的最大分数是多少？请输出这个最大值。

输入按以下格式从标准输入给出。 > $N$ $S$ $Q$ $X_1$ $Y_1$ $Z_1$ $X_2$ $Y_2$ $Z_2$ $\vdots$ $X_Q$ $Y_Q$ $Z_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 - 第 $1$ 个询问中，将 `?` 替换为 `ABCBABCBA` 后，可获得分数 $8$。 - 第 $2$ 个询问中，将 `?` 替换为 `ABABAACAA` 后，可获得分数 $6$。 - 第 $3$ 个询问中，将 `?` 替换为 `ACCBCCCCA` 后，可获得分数 $4$。 ### 数据范围 - $N, Q, X_i, Y_i, Z_i$ 均为整数。 - $2 \leq N \leq 3 \times 10^5$。 - $S$ 仅包含 `A`、`B`、`C`、`?`。 - $S$ 的第 $1$ 个和第 $N$ 个字符都是 `A`。 - $1 \leq Q \leq 2 \times 10^5$。 - $0 \leq X_i$。 - $0 \leq Y_i$。 - $0 \leq Z_i$。 - $X_i + Y_i + Z_i$ 等于 $S$ 中 `?` 的个数。 由 ChatGPT 5 翻译