You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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}$。

2 3
ABABBAABB
3
8
4

B
B
A

2 5
AAAAAAAAA
1
2
7
8
5

A
A
A
B
B

1 4
AAB
3
1
2
3

A
A
B
B

3 6
AABABABBABAABABBBBBBAABABAA
4
1
9
3
8
9

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】

该样例满足子任务 $2,5$ 的限制。

【数据范围】

• $1\le N\le 12$；
• $1\le Q\le 2\times 10^5$；
• $T$ 是长度为 $3^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<l\le Q)$；
5. （$25$ 分）无附加限制。