Problem G
Government Help
Two major banks in our country are knee-deep in troubles. We will call them “Bank A” and “Bank B” – hopefully you understand we absolutely cannot tell you their real names. It might ruin them.
As a logical consequence of their troubles, government comes to rescue them, preparing a set of financial “packages” that will be distributed between these two banks. However, there is one important condition: the packages will be given to the banks one by one and we need to minimize the difference between the amount given to both banks in any particular moment. Otherwise, one of the banks would gain a big advantage over the other.
For example, imagine that we have four packages with the values of $100\, 000$, $110\, 000$, $120\, 000$, and $150\, 000$. If we give the first package to the Bank A, then the second one to the Bank B, the third one to the Bank B, and the fourth package to the Bank A, the difference between the help provided to the banks will be $+100\, 000$ after the first package, $-10\, 000$ after the second one, $-130\, 000$ after the third one, and $+20\, 000$ after the last package. The maximal difference is therefore $130\, 000$.
There is a better solution, with the maximal difference of $100\, 000$ only: first, give $100\, 000$ to the Bank A, then $120\, 000$ to the Bank B, then $110\, 000$ to the Bank A, and then $150\, 000$ to the Bank B.
Input
The input contains multiple sets of financial packages. Each set begins with a line containing a single positive integer $N$: the number of financial packages ($1 \leq N \leq 50\, 000$). The second line is a set of $N$ positive integers separated by a space, all of them between $100\, 000$ and $199\, 999$ inclusive. These numbers specify the amount of money in individual packages. Packages can be assigned in any order, the order of numbers on the second line is therefore not important. The last set will be followed by a line containing single zero.
Output
For each set of financial packages, output one line containing the order of assignments of packages to the banks, such as the maximal difference is as low as possible. If there are more possible solutions, you may print any of them.
Assignments must be separated by a space, each assignment consists of one number (the package size), one dash character (“-”), and an uppercase letter (“A” or “B”) specifying the bank.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 100000 110000 120000 150000 3 100000 100000 100000 0 |
100000-A 150000-B 120000-A 110000-B 100000-A 100000-B 100000-A |