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
different things that can go wrong with the computer, and any
subset of those
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 and phase A is a repeating sequence of ones followed by zeros. Similarly, a square wave
with period and phase
B is a repeating sequence of
zeros followed by
ones. For example,
the following is a square wave with period and phase A:
and the following is a square wave with period and with phase B:
If problem
() occurs,
the computer generates a square wave with a period of
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 which it then plays
using the speaker. For example, if the previous two example
square waves are summed, the following sequence would
result:
The recording you need to analyze is a prefix of the
infinite sequence . 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
, , the length of the
recording. The second line contains integers , where .
Output
The output should consist of characters (separated by spaces),
where character
indicates what you were able to determine about problem
. 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
|