# Problem A

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:

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