K. Knapsack
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

$$$n=10^4$$$ integers $$$a_1, a_2, ..., a_n$$$ are randomly and independently generated from the range $$$[1..10^{12}]$$$.

For each integer, you need to either discard it or put it into one of the sets $$$A$$$, $$$B$$$, or $$$C$$$. The sum of the integers in the set $$$A$$$ should be equal to the sum in the set $$$B$$$ and equal to the sum in the set $$$C$$$.

Each set should contain at least one integer. If there are multiple solutions, you could print any of them. It is guaranteed that the answer always exists for all tests in the system.

Input

The first line contains one integer $$$n$$$ ($$$n = 10^4$$$ or $$$n = 6$$$) — the number of elements in the array.

The second line contains integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^{12}$$$).

All tests except the sample are guaranteed to have $$$n=10^4$$$, and integers $$$a_i$$$ are randomly generated from a uniform distribution.

Output

Print one line consisting of $$$n$$$ characters. For each integer, print "." if you want to discard it. Otherwise, print "A", "B" or "C" to indicate the set to put this integer.

Example
Input
6
4 3 8 1 5 4
Output
ABC.BA
Note

This problem has one sample test and $$$50$$$ real test cases.