← 返回题目列表

AtCoder · joig2025_c

C. 修学旅行

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOIG 高中 编号至 1 从 3^N 有 3^N 名学生。

JOIG 高中旅行有两种选择:A计划去阿拉斯加,B计划去玻利维亚,我们如下决定去哪一个。

  • 长度 3^N 字符串 S 致学生 i (1 \leqq i \leqq 3^N) 想要选项 A。 i 第一个字符是 A ,如果你想要B计划 通过设置 i 第一个字符是 B 进行定义。
  • 执行以下操作 执行 N 次。
    • (操作):当前 S 的长度 X ,长度 \frac{X}{3} 字符串 S' , S' 的 j (1\leqq j \leqq \frac{X}{3}) S 的 3j - 2, 3j - 1, 3j 由出现次数最多的字符决定。 替换为S 它被转换为格式 S' 。
  • 操作 经过 N 次后 S 是 仅由 A 或 B ,A 然后,按照计划A,B 然后,决定B计划。

首先,这取决于每个学生喜欢的计划长度。 它被给出为 3^N 字符串 T 。T 的 i 第一个字母是学生 如果 i 想要计划A。 A,如果你想要B计划 B 。此后,Q 事件发生。k (1 \leqq k \leqq Q) 在第二次活动中,学生 更改 p_k 所需的计划。也就是说,k 活动前夕的学生 p_k 期望的计划是 A 奈良学生 p_k 想要的计划 B ,否则 更改为 A 。 关于

k=1,2,\ldots,Q ,k 创建一个程序,在第一个活动结束时根据每个学生的意愿确定学校旅行的目的地时将选择哪个选项。但是,请注意,对您所需计划的更改不是暂时的,并且会影响后续事件。

制約

  • 1 \leqq N \leqq 12.
  • 1 \leqq Q \leqq 200\,000.
  • T 是长度 它是一个 3^N 字符串。
  • T 中的每个字符是 A 或 B 。
  • 1 \leqq p_k \leqq 3^N (1 \leqq k \leqq Q).
  • N, Q, p_k 是一个整数。

小課題

  1. (8 点) N = 1.
  2. (17 点) Q \leqq 10.
  3. (22 点) p_k \leqq 5 (1 \leqq k \leqq Q).
  4. (28 点) T 中的每个字符是 A 。另外,p_k \neq p_l (1\leqq k < l\leqq Q).
  5. (25 点)没有额外的限制。

入力

输入按以下格式给出。

N Q
T
p_1
p_2
\vdots
p_Q

出力

Q 跨线输出。k\,(1 \leqq k \leqq Q) 行中,k 如果在第一次活动结束时根据每个学生的意愿决定修学旅行的目的地,并选择A计划, A ,如果选择选项 B,则 B 。


入力例 1

2 3
ABABBAABB
3
8
4

出力例 1

B
B
A

1 如果在第一次活动结束时根据每个学生的意愿来确定修学旅行的目的地,我们可以看到选择的方案 B 如下。

  • 最初,文字列 S 是 仅由 ABBBBAABB 。
  • 1 操作后,S 是 仅由 BBB 变为。
  • 2 操作后,S 是 仅由 B 变为。
  • 因此选择B方案。

2 如果在第一次活动结束时根据每个学生的意愿来确定修学旅行的目的地,我们可以看到选择的方案 B 如下。

  • 最初,文字列 S 是 仅由 ABBBBAAAB 。
  • 1 操作后,S 是 仅由 BBA 变为。
  • 2 操作后,S 是 仅由 B 变为。
  • 因此选择B方案。

3 如果在第一次活动结束时根据每个学生的意愿确定修学旅行的目的地,我们可以看到选择的计划 A 如下。

  • 最初,文字列 S 是 仅由 ABBABAAAB 。
  • 1 操作后,S 是 仅由 BAA 变为。
  • 2 操作后,S 是 仅由 A 变为。
  • 因此,选择方案A。

此输入示例是一个小作业。 2, 5 满足约束。


入力例 2

2 5
AAAAAAAAA
1
2
7
8
5

出力例 2

A
A
A
B
B

此输入示例是一个小作业。 2, 4, 5 满足约束。


入力例 3

1 4
AAB
3
1
2
3

出力例 3

A
A
B
B

此输入示例是一个小作业。 1, 2, 3, 5 满足约束。


入力例 4

3 6
AABABABBABAABABBBBBBAABABAA
4
1
9
3
8
9

出力例 4

B
B
B
B
B
A

此输入示例是一个小作业。 2, 5 满足约束。