Quarter-Finals
with Brazil!? No!!! |

The FIFA World Cup of Germany 2006 is just going to start! This time, Spain cannot fail! We have to win the cup, even though we meet Brazil in quarter-finals... Now, seriously, everybody knows the "Canarinha" (Brazilian national football team) is the best team. But still we can play with statistics and probabilities. For example, the German organizers (that are not so good as Brazil but very clever people) have arranged the competition so that eventually Germany and Brazil could only meet in the final. Very clever, indeed.

In this problem you will have to organize a Football World Cup, maximizing the probability that our team wins the cup.

2^{N} teams participate in a cup competition
with *N* rounds. The teams are denoted by A, B, C, D, etc.
An arrangement of the competition is given by a string, e.g.
"ABCD", "BDAC" or "BA". For
example, the string "ABCDEFGH" means that in first
round the matches are (A vs. B), (C vs. D), (E vs. F), ..., in
the second round (winner(A,B) vs. winner(C,D)), and so on.

We have scored all the teams with integer positive numbers, s(x); the greater the better. For each pair of teams, A and B, we assume the probability that A beats B is given by the following: P(A wins B)= s(A)/(s(A)+s(B))

Using this basic probability, we can compute the probability that A wins one round, two rounds, three rounds, and eventually the probability to win the cup. For example, for the arrangement "ABCD" the probability that A wins the cup is:

P(A wins "ABCD")= P(A wins B)*(P(A wins C)*P(C wins D) + P(A wins D)*P(D wins C))

You have to compute the arrangement that maximizes the probability that our team wins the cup. If more than one arrangement is possible, you have to give the alphabetically first one.

The first line of the input contains an integer *M*,
indicating the number of test cases.

For each test case, the first line contains an integer *N*,
between 1 and 5, indicating the number of rounds in the
competition. The second line contains a single character,
indicating the letter of our team. Then, we have a line with 2^{N}
integers indicating the scores of the teams, starting with A,
that is: s(A), s(B), s(C), and so on. In the case *N*=5,
lowercase letters are used to denote the teams form 27 to 32; and
those letters are considered to be alphabetically greater than
uppercase letters. That is, the teams in order are: A, B, C, D,
E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
a, b, c, d, e, f.

For each test case, the output should consist of a string with
2^{N} characters, representing the desired
arrangement. Remember that you have to output the alphabetically
first possibility, if the solution is not unique.

10 2 A 7 3 1 9 2 C 44 44 44 44 3 E 8 9 8 9 7 8 9 8 3 B 8 9 8 9 7 8 9 8 4 B 41 23 57 14 50 10 49 57 51 54 41 61 52 32 7 58 4 D 6 8 10 6 5 6 2 8 5 3 3 2 9 9 6 10 2 B 7 16 30 18 5 Y 3 5 46 30 51 66 61 27 63 27 57 63 11 31 36 39 43 28 1 28 65 53 21 10 3 52 58 32 64 19 52 42 4 A 12 29 46 9 20 61 52 35 3 46 45 23 40 6 50 39 5 F 20 17 24 3 7 23 23 28 5 10 12 21 12 21 8 16 1 28 11 10 27 15 1 18 24 21 13 1 18 13 17 20

ACBD ABCD ABDGCEFH ACBEDGFH AGKNBODFCHLPEIJM AEIJDGKLBHFOCPMN ABCD ABSYMXWdDNObHJRTCQPfEZVeFUIcGLKa AIDNBHELCKMPFGJO ALXfBPceCGNZHRUYDIEOFQWbJTKSMaVd