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.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 keep bread bye bed beat sad |
sad bread bed beat keep bye |
