Lester is the principal of the School of Imposture. This year, the school has admitted $N$ students who will be trained to become sussy impostors.

Each incoming student has a unique name. To better organize the school's data, Lester wants to list the students' names using a particular ordering. Suppose there are two names $S$ and $T$. The name $S$ should appear before $T$ if $|S| < |T|$ (the length of $S$ is shorter than that of $T$). Otherwise, if the lengths of $S$ and $T$ are the same, the name $S$ should appear before $T$ if $S$ would be placed before $T$ in a dictionary (alphabetical order).

Given the names of all incoming students, generate the list of names that satisfies the required ordering.

Input

The first line of input contains only one integer $N$. $(1 \le N \le 10^5)$
Each of the next $N$ lines of input contain the name of an incoming student, consisting of at most 10 lowercase English letters.

Output

Output $N$ lines where each line contains a student's name. The list of names should satisfy the required ordering.