JOIG High School Trip Selection

There are \(3^N\) students in JOIG High School, numbered from \(1\) to \(3^N\). The school will organize a trip, and there are two potential destinations: Alaska (option \(A\)) and Bolivia (option \(B\)).

The decision process is as follows:

1. Consider a string \(S\) of length \(3^N\) where the \(i\)-th character is \(A\) if student \(i\) chooses option \(A\), and \(B\) otherwise.
2. Perform the following operation \(N\) times: Suppose the current string \(S\) has length \(X\). Construct a new string \(S'\) of length \(\frac{X}{3}\) where, for each \(1 \le j \le \frac{X}{3}\), \(S'_j\) is the majority character among \(S_{3j-2}\), \(S_{3j-1}\), and \(S_{3j}\). Since there are only two characters, the majority is well-defined.
3. After \(N\) operations, the string \(S\) becomes a single character. If it is \(A\), the final chosen destination is Alaska; otherwise, it is Bolivia.

Initially, a string \(T\) of length \(3^N\) indicates each student's choice. Then, \(Q\) events occur. In the \(k\)-th event, the student at position \(p_k\) toggles his/her choice (i.e. changes \(A\) to \(B\) or \(B\) to \(A\)). After each event, determine the final travel destination by applying the above process.

inputFormat

The first line contains two integers \(N\) and \(Q\).

The second line contains a string \(T\) of length \(3^N\) consisting only of characters \(A\) and \(B\).

Each of the following \(Q\) lines contains an integer \(p_k\) (\(1 \le p_k \le 3^N\)) indicating the student whose choice is toggled in the \(k\)-th event.

outputFormat

For each event, output a line containing a single character \(A\) or \(B\) representing the final travel destination after that event.

sample

1 1
ABA
2

A