Hide

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:

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 

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

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 

If problem k (1k20) occurs, the computer generates a square wave with a period of 2k 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 a1,a2, which it then plays using the speaker. For example, if the previous two example square waves are summed, the following sequence a1,a2, would result:

1 2 0 1 1 2 0 1 1 2 0 1 1 2 0 1 

The recording you need to analyze is a prefix of the infinite sequence a1,a2,. 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, 2N220, the length of the recording. The second line contains N integers a1,,aN, where 0ai20.

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
Hide

Please log in to submit a solution to this problem

Log in