AT_joig2025_c 修学旅行 (School Trip)

JOIG 高中有 $3^N$ 名学生，每位学生都被分配了 $1$ 到 $3^N$ 的编号。 学校计划修学旅行的目的地有两个方案：提案 A（去阿拉斯加）和提案 B（去玻利维亚）。决定去哪一个方案的方法如下： - 用一个长度为 $3^N$ 的字符串 $S$ 标记每位学生的意愿。第 $i$ 位学生若支持提案 A，则 $S$ 的第 $i$ 个字符为 `A`，若支持提案 B，则为 `B`。 - 进行 $N$ 次如下操作： - （操作）：令当前 $S$ 的长度为 $X$，构造长度为 $\frac{X}{3}$ 的新字符串 $S'$。对于 $j$（$1 \leq j \leq \frac{X}{3}$），$S'$ 的第 $j$ 个字符取 $S$ 的第 $3j-2$、$3j-1$、$3j$ 这三位中出现较多的那个字符。然后用 $S'$ 替换 $S$。 - $N$ 次操作后，$S$ 会只剩下一个字符，该字符为 `A` 则采用提案 A，为 `B` 则采用提案 B 作为旅行目的地。 最初，每位学生的意愿由一个长度为 $3^N$ 的字符串 $T$ 给出，$T$ 的第 $i$ 位若为 `A` 则表示第 $i$ 位学生希望 A，若为 `B` 则希望 B。接下来会有 $Q$ 次事件编号 $k$（$1 \leq k \leq Q$），每次事件会改变编号为 $p_k$ 的学生的意愿：如果该学生原本希望 A，则更改为 B；若原本希望 B，则更改为 A（注意，改变是持续生效的，会影响后续事件）。 请你编写程序，对于每一次事件后的学生意愿，按照上述方式决定旅行目的地，并输出对应选择的方案（`A` 或 `B`）。

输入格式如下： > $N$ $Q$ > $T$ > $p_1$ > $p_2$ > $\vdots$ > $p_Q$

输出共 $Q$ 行。第 $k$ 行输出第 $k$ 次事件后，根据当前学生意愿决定出的最终方案，若为 A 则输出 `A`，为 B 则输出 `B`。

### 小提示 1. ($8$ 分) $N = 1$。 2. ($17$ 分) $Q \leq 10$。 3. ($22$ 分) $p_k \leq 5$（$1 \leq k \leq Q$）。 4. ($28$ 分) $T$ 中所有字符均为 `A`，且 $p_k \neq p_l$（$1 \leq k < l \leq Q$）。 5. ($25$ 分) 无其他限制。 ### 样例解释 1 第一次事件后，根据所有学生的当前意愿判断，最终方案为 B，详细如下： - 最初字符串 $S$ 为 `ABBBBAABB`。 - 第一次操作后，$S$ 变为 `BBB`。 - 第二次操作后，$S$ 变为 `B`。 - 因此，选择方案 B。 第二次事件后，所有学生的当前意愿对应最终方案也为 B，过程如下： - 最初字符串 $S$ 为 `ABBBBAAAB`。 - 第一次操作后，$S$ 变为 `BBA`。 - 第二次操作后，$S$ 变为 `B`。 - 因此，选择方案 B。 第三次事件后，根据所有学生的当前意愿判断，最终方案为 A，过程如下： - 最初字符串 $S$ 为 `ABBABAAAB`。 - 第一次操作后，$S$ 变为 `BAA`。 - 第二次操作后，$S$ 变为 `A`。 - 因此，选择方案 A。 此组数据符合第 $2,5$ 小题的限制。 ### 样例解释 2 此组数据符合第 $2,4,5$ 小题的限制。 ### 样例解释 3 此组数据符合第 $1,2,3,5$ 小题的限制。 ### 样例解释 4 此组数据符合第 $2,5$ 小题的限制。 ### 数据范围与约定 - $1 \leq N \leq 12$。 - $1 \leq Q \leq 200\,000$。 - $T$ 为长度为 $3^N$ 的字符串。 - $T$ 的各字符均为 `A` 或 `B`。 - $1 \leq p_k \leq 3^N$（$1 \leq k \leq Q$）。 - $N,Q,p_k$ 均为整数。 由 ChatGPT 5 翻译