Diatribe against Pigeonholes

In an anonymous town there is a carpenter, the only one in many kilometres, specialized in making pieces of furniture (and famous for being a bit stingy with the screws). This carpenter made a shelving for a company, using only two screws. We have a lineal set of N similar pigeonholes (numbered 1,2,3,...,N, with 1 < N < 26) forming a shelving, where N workers of a company receive their mail. Each worker has an associated capital letter, A, B, C, and so on, until Z if necessary. Your task is to associate each worker with one pigeonhole. As the shelving is fragile in the middle (i.e., pigeonhole (N + 1)/2) due to the stinginess of the carpenter, we have to put the mail of each worker as follows: the heaviest ones, the further from the middle of the shelving, in order to protect the shelving. You must suppose that all parcels weigh the same weight. Input The first line of the input contains an integer, M, indicating the number of test cases. For each test case, the first line indicates the number N of workers (and pigeonholes) of the company, 1 < N < 26. One more line follows, containing a string of capital letters, corresponding each one with a parcel destinated to the corresponding worker, finished with a ‘#’ character. For example, the string ‘ABABBAA#’ means that worker A receives 4 parcels, and B receives 3. Characters not corresponding with valid workers must be omitted. Output For each test case, the output should consist of two lines, the first one showing the secuence of workers corresponding with the obtained ordering, separated with one blank space. If there is more than one solution, you have to output the alphabetically first. The second line will consist of the number of parcels in each pigeonhole, in the same order of the previous line, and also separated with one blank space. Sample Input 4 5 BDCECDCBCBCDECDABCEDVBCDBCDBCDABCAED# 7 BGFADCEDGFCDEGCFCGDGCXXDAEDACEACEGFAGFCEDGCEDGBCD# 24 AABACDEDFGHMMJNTBNHGTDFACCDLLPPPERRAMMMMKKKKJJJHHHAAAAGGGQQQLLLLPPPAA# 10 PDJFGEDFANGEHIAEJBHJGEDGJGJEINDFJHEIEDGHFFGHDHGFHAJGIE# Sample Output CBAED 11 8 3 4 9 CDABFEG 10 9 5 2 5 7 9 ALGDCBEFIOSUVWXNRTQJKHMP 11 6 5 4 3 2 2 2 0 0 0 0 0 0 0 2 2 2 3 4 4 5 6 6

2/2 EHDABCIFJG 8763104679