Hide

Problem K
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:

\begin{equation*} 1~ 1~ 0~ 0~ 1~ 1~ 0~ 0~ 1~ 1~ 0~ 0~ 1~ 1~ 0~ 0~ \dots \end{equation*}

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

\begin{equation*} 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~ 0~ 1~ \dots \end{equation*}

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:

\begin{equation*} 1~ 2~ 0~ 1~ 1~ 2~ 0~ 1~ 1~ 2~ 0~ 1~ 1~ 2~ 0~ 1~ \dots \end{equation*}

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 ?.

Sample Input 1 Sample Output 1
4
1 2 0 1
B A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Sample Input 2 Sample Output 2
17
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1
B x x x B ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Sample Input 3 Sample Output 3
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

Please log in to submit a solution to this problem

Log in