Problem E
Beep Code

Aecepece is having computer problems. Their computer will not turn on, and is producing a beeping sound which is supposed to help diagnose the issue, but they cannot seem to analyze it by ear. Your task is to analyze a recording of this beeping sound to determine what the problems are.

There are $20$ different things that can go wrong with the computer, and any subset of those $20$ problems may actually be occurring. Additionally, for each problem which occurs, the computer will indicate that it is due to one of two reasons: A or B. The problems are indicated by square waves with a specific period and phase. A square wave with period $p$ and phase A is a repeating sequence of $p/2$ ones followed by $p/2$ zeros. Similarly, a square wave with period $p$ and phase B is a repeating sequence of $p/2$ zeros followed by $p/2$ ones. For example, the following is a square wave with period $4$ and phase A:

and the following is a square wave with period $2$ and with phase B:

If problem $k$ ($1\le k\le 20$) occurs, the computer generates a square wave with a period of $2^k$ and with phase matching the reason for the problem. The computer generates waves for all problems which are occurring and sums them to produce an integer sequence $a_1,a_2,\dots$ which it then plays using the speaker. For example, if the previous two example square waves are summed, the following sequence $a_1,a_2,\dots$ would result:

The recording you need to analyze is a prefix of the infinite sequence $a_1,a_2,\dots$. However, Aecepece is not sure if they made a long enough recording to detect all of the problems. You should determine as much as you can from it.

Input

The first line of input contains a single integer $N$, $2\le N\le 2^{20}$, the length of the recording. The second line contains $N$ integers $a_1,\dots ,a_N$, where $0\le a_i\le 20$.

Output

The output should consist of $20$ characters (separated by spaces), where character $k$ indicates what you were able to determine about problem $k$. If the problem did not occur, write x. If it occurred, write A or B to denote the reason. If the recording was not long enough to determine with certainty whether the problem occurred, write ?.

4
1 2 0 1

B A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

17
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

B x x x B ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

8
19 18 20 19 18 17 19 18

A B A A A A A A A A A A A A A A A A A A