「JOIG 2025」修学旅行 / School Trip - Problem

题目描述

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$ 次事件发生后，按照上述流程，学校会选择哪个旅行方案。

输入格式

第一行输入两个整数 $N,Q$。

第二行输入一个字符串 $T$。

接下来 $Q$ 行，每行一个整数 $p_k$。

输出格式

输出 $Q$ 行，第 $k(1\le k\le Q)$ 行一个字符串表示第 $k$ 次事件过后学校选择的旅行方案：如果为 $\texttt{A}$，那么学校选择方案 $\texttt{A}$；如果为 $\texttt{B}$，那么学校选择方案 $\texttt{B}$。

输入输出样例 #1

输入 #1

2 3
ABABBAABB
3
8
4

输出 #1

B
B
A

输入输出样例 #2

输入 #2

2 5
AAAAAAAAA
1
2
7
8
5

输出 #2

A
A
A
B
B

输入输出样例 #3

输入 #3

输出 #3

A
A
B
B

输入输出样例 #4

输入 #4

3 6
AABABABBABAABABBBBBBAABABAA
4
1
9
3
8
9

输出 #4

B
B
B
B
B
A

说明/提示

【样例解释 #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】