Problem A
Signs

Tom has $N$ signs and he wants to hang all of them on a pole center-aligned. Also, he wants the signs to be "sorted alphabetically". This means the signs are ordered according to the middle letter(s). If the sign has an even number of characters on it, the middle 2 letters are considered, but only 1 letter is considered otherwise. All other letters are ignored, for the purpose of "sorting". If two signs have the same middle letter(s), relative to each other, they should appear in the same order as given in the input.

Input

The first line contains $1\le N\le 50,000$, the number of signs. On each of the next $N$ lines is the contents of a sign made up of only lowercase letters, each sign having between 1 to 20 letters inclusive.

Output

Print the (left-aligned) contents of the signs according to the order for which Tom would like to display them, one sign on each line.

6
keep
bread
bye
bed
beat
sad

sad
bread
bed
beat
keep
bye