Given a list of English words, rearrange the words in lexicographic (dictionary) order, which is similar to how the English words are listed in an English dictionary. That is, given two words W1 and W2, we compare them character by character. If the ASCII code of the first character of W1 is smaller than the first character of W2, we said that W1 is smaller than W2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order. If W1 is W2’s prefix, then W1 is smaller than W2, for example, “cool” is a prefix of “coolness” so “cool” is considered to be smaller than “coolness”.
There are multiple test cases. Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line. The maximum length of words is 50. The alphabets are 26 lowercase letters ‘a’ to ‘z’. The input ends when N = 0.
For each test case, print the words in lexicographic order. Print a blank line after each case.