日本情報オリンピック 第5回 女性部門

2025年2月8日
情報オリンピック日本委員会

問題文

JOIG 高校には 1 から 3^N までの番号がつけられた 3^N 人の生徒がいる．

JOIG 高校の修学旅行の行き先として，アラスカに行く案 A とボリビアに行く案 B があり，どちらにするかを以下のように決定することにした．

• 長さ 3^N の文字列 S を生徒 i (1 ≦ i ≦ 3^N) が案 A を希望するなら i 文字目は A に，案 B を希望するなら i 文字目は B にすることで定める．
• 次の操作を N 回行う．
  • （操作）：現在の S の長さを X として，長さ X ÷ 3 の文字列 S' を， S' の j (1≦ j ≦ 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 ≦ k ≦ Q) 回目のイベントでは，生徒 p_k の希望する案を変更する．すなわち，k 回目のイベントの直前での生徒 p_k の希望する案が A なら生徒 p_k の希望する案を B に，そうでないなら A に変更する．

k=1,2,...,Q について，k 回目のイベントが終わった時点での各生徒の希望をもとに修学旅行の行き先を決定した場合にどちらの案が選ばれるかを求めるプログラムを作成せよ．ただし，希望案の変更は一時的なものではなく，その後のイベントに影響することに注意せよ．

制約

• 1 ≦ N ≦ 12．
• 1 ≦ Q ≦ 200 000．
• T は長さ 3^N の文字列である．
• T の各文字は A または B のいずれかである．
• 1 ≦ p_k ≦ 3^N (1 ≦ k ≦ Q)．
• N, Q, p_k は整数である．

小課題

1. (8 点) N = 1．
2. (17 点) Q ≦ 10．
3. (22 点) p_k ≦ 5 (1 ≦ k ≦ Q)．
4. (28 点) T の各文字は A である．また，p_k ≠ p_l (1 ≦ k ＜ l ≦ Q)．
5. (25 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N Q
T
p₁
p₂
︙
p_Q

出力

Q 行にわたって出力せよ．k  (1 ≦ k ≦ 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 の制約を満たす．