| 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.
2N 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 2N 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 2N 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