题目描述
JOIG 高中有 3N 名学生,编号从 1 到 3N。
JOIG 高中决定举行一场学校旅行,有两个可能的旅行目的地:阿拉斯加(记为“方案 A”)和玻利维亚(记为“方案 B”)。学生们决定使用以下的流程确定最终的旅行方案:
- 考虑一个长度为 3N 的字符串 S:如果学生 i(1≤i≤3N) 选择方案 A,那么 Si 为 A,否则为 B;
- 执行以下操作 N 次:
- 假设当前 S 的长度为 X,考虑一个长度为 3X 的字符串 S′,满足 Sj′(1≤j≤3X) 为 S3j−2,S3j−1,S3j 中出现次数较多的字符(A 或 B);接着将 S 替换为 S′;
- 所有操作结束之后,S 将成为一个长度为 1 的字符串(要么为 A 要么为 B);如果 S 为 A,那么学校最终选取方案 A,否则选取方案 B。
初始时,我们使用一个字符串 T 表示每名学生选择哪个方案:如果学生 i(1≤i≤3N) 选择方案 A,那么 Ti 为 A,否则为 B。
之后依次发生了 Q 次事件,第 k(1≤k≤Q) 次事件中,学生 pk(1≤pk≤3N) 改变了其选择的方案,即若原来他 / 她选择方案 A,那么现在他 / 她选择的方案变为 B,反之亦然。
对于 k=1,2,…,Q,求出第 k 次事件发生后,按照上述流程,学校会选择哪个旅行方案。
输入格式
第一行输入两个整数 N,Q。
第二行输入一个字符串 T。
接下来 Q 行,每行一个整数 pk。
输出格式
输出 Q 行,第 k(1≤k≤Q) 行一个字符串表示第 k 次事件过后学校选择的旅行方案:如果为 A,那么学校选择方案 A;如果为 B,那么学校选择方案 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 的变化为 ABBBBAABB→BBB→B,最终选取方案 B;
- 在第 2 次事件发生后,确定方案流程中,S 的变化为 ABBBBAAAB→BBA→B,最终选取方案 B;
- 在第 3 次事件发生后,确定方案流程中,S 的变化为 ABBABAAAB→BAA→A,最终选取方案 A。
该样例满足子任务 2,5 的限制。
【样例解释 #2】
该样例满足子任务 2,4,5 的限制。
【样例解释 #3】
该样例满足子任务 1,2,3,5 的限制。
【样例解释 #4】
该样例满足子任务 2,5 的限制。
【数据范围】
- 1≤N≤12;
- 1≤Q≤2×105;
- T 是长度为 N 且仅包含大写字母 A 和 B 的字符串;
- 1≤pk≤3N(1≤k≤Q)。
【子任务】
- (8 分)N=1;
- (17 分)Q≤10;
- (22 分)pk≤5(1≤k≤Q);
- (28 分)T 中所有字符均为 A 且之后的修改均满足 pk=pl(1≤k<l≤Q);
- (25 分)无附加限制。