P11725 [JOIG 2025] 修学旅行 / School Trip

JOIG 高中有 $3^N$ 名学生，编号从 $1$ 到 $3^N$。 JOIG 高中决定举行一场学校旅行，有两个可能的旅行目的地：阿拉斯加（记为“方案 $\texttt{A}$”）和玻利维亚（记为“方案 $\texttt{B}$”）。学生们决定使用以下的流程确定最终的旅行方案： - 考虑一个长度为 $3^N$ 的字符串 $S$：如果学生 $i\left(1\le i\le 3^N\right)$ 选择方案 $\texttt{A}$，那么 $S_i$ 为 $\texttt{A}$，否则为 $\texttt{B}$； - 执行以下操作 $N$ 次： - 假设当前 $S$ 的长度为 $X$，考虑一个长度为 $\frac{X}{3}$ 的字符串 $S'$，满足 $S'_j\left(1\le j\le\frac{X}{3}\right)$ 为 $S_{3j-2},S_{3j-1},S_{3j}$ 中出现次数较多的字符（$\texttt{A}$ 或 $\texttt{B}$）；接着将 $S$ 替换为 $S'$； - 所有操作结束之后，$S$ 将成为一个长度为 $1$ 的字符串（要么为 $\texttt{A}$ 要么为 $\texttt{B}$）；如果 $S$ 为 $\texttt{A}$，那么学校最终选取方案 $\texttt{A}$，否则选取方案 $\texttt{B}$。 初始时，我们使用一个字符串 $T$ 表示每名学生选择哪个方案：如果学生 $i\left(1\le i\le 3^N\right)$ 选择方案 $\texttt{A}$，那么 $T_i$ 为 $\texttt{A}$，否则为 $\texttt{B}$。 之后依次发生了 $Q$ 次事件，第 $k(1\le k\le Q)$ 次事件中，学生 $p_k\left(1\le p_k\le 3^N\right)$ 改变了其选择的方案，即若原来他 / 她选择方案 $\texttt{A}$，那么现在他 / 她选择的方案变为 $\texttt{B}$，反之亦然。 对于 $k=1,2,\ldots,Q$，求出第 $k$ 次事件发生后，按照上述流程，学校会选择哪个旅行方案。

无

无

#### 【样例解释 #1】 - 在第 $1$ 次事件发生后，确定方案流程中，$S$ 的变化为 $\texttt{ABBBBAABB}\to\texttt{BBB}\to\texttt{B}$，最终选取方案 $\texttt{B}$； - 在第 $2$ 次事件发生后，确定方案流程中，$S$ 的变化为 $\texttt{ABBBBAAAB}\to\texttt{BBA}\to\texttt{B}$，最终选取方案 $\texttt{B}$； - 在第 $3$ 次事件发生后，确定方案流程中，$S$ 的变化为 $\texttt{ABBABAAAB}\to\texttt{BAA}\to\texttt{A}$，最终选取方案 $\texttt{A}$。 该样例满足子任务 $2,5$ 的限制。 #### 【样例解释 #2】 该样例满足子任务 $2,4,5$ 的限制。 #### 【样例解释 #3】 该样例满足子任务 $1,2,3,5$ 的限制。 #### 【样例解释 #4】 该样例满足子任务 $2,5$ 的限制。 #### 【数据范围】 - $1\le N\le 12$； - $1\le Q\le 2\times 10^5$； - $T$ 是长度为 $N$ 且仅包含大写字母 $\texttt{A}$ 和 $\texttt{B}$ 的字符串； - $1\le p_k\le 3^N(1\le k\le Q)$。 #### 【子任务】 1. （$8$ 分）$N=1$； 2. （$17$ 分）$Q\le 10$； 3. （$22$ 分）$p_k\le 5(1\le k\le Q)$； 4. （$28$ 分）$T$ 中所有字符均为 $\texttt{A}$ 且之后的修改均满足 $p_k\ne p_l(1\le k