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:
\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 |
