35351번 - 修学旅行 (School Trip) 서브태스크다국어

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

入力は以下の形式で与えられる．

N Q

T

p₁

p₂

︙

p_Q

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

• 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 は整数である．