Here we consider the strings composed of only characters ‘A’, ‘C’, ‘G’ and ‘T’. In the alphabetical order, ‘A’ is in front of ‘C’, ‘C’ is in front of ‘G’, and ‘G’ is in front of ‘T’. The “unsortedness” of a string is the number of pairs of characters that are out of alphabetical order with respect to each other. For example, the “unsortedness” of “ACACA” is 3, because the first ‘C’ is in front of two ‘A’s, and the second ‘C’ is in front of one ‘A’.
Given N strings, sort them in the ascending order of strings’ “unsortedness”. For example, given “AACATGAAGG” and “CCCGGGGGGA”, output
CCCGGGGGGA
AACATGAAGG
because the unsortedness of “AACATGAAGG” is 3+5+2=10, and the unsortedness of “CCCGGGGGGA” is 9.
The input includes multiple test cases. In each test case, the first line contains two integers, N and L, which indicate the number of strings, and the length of every string. (1 <= N <= 105, 1 <= L <= 10.) The next N lines follow. Every line contains one string composed of the characters ‘A’, ‘C’, ‘G’ and ‘T’.
For each test case, output the sorted results in N lines, one string per line. If the unsortedness of two strings are the same, sort them in lexicographically order.