AT_joig2025_c 修学旅行 (School Trip)

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 $ 回目のイベントが終わった時点での各生徒の希望をもとに修学旅行の行き先を決定した場合にどちらの案が選ばれるかを求めるプログラムを作成せよ．ただし，希望案の変更は一時的なものではなく，その後のイベントに影響することに注意せよ．

入力は以下の形式で与えられる． > $ N $ $ Q $ $ T $ $ p_1 $ $ p_2 $ $ \vdots $ $ p_Q $

$ Q $ 行にわたって出力せよ． $ k\,(1 \leqq k \leqq Q) $ 行目には， $ k $ 回目のイベントが終わった時点での各生徒の希望をもとに修学旅行の行き先を決定した場合に案 A が選ばれる場合は `A` を，案 B が選ばれる場合は `B` を出力せよ．

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 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 $ の制約を満たす． ### Sample Explanation 2 この入力例は小課題 $ 2, 4, 5 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 1, 2, 3, 5 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 2, 5 $ の制約を満たす． ### Constraints - $ 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 $ は整数である．