Sorting the Jewelry

Interview

Time limit1sMemory limit512 MB

Summary

Sort up to 150 lowercase strings by increasing length, breaking ties in lexicographic order.

Level: Easy3 of 10
Topics: Sorting
Solved: No attempts yet

Problem

Malgosia inherited a collection of precious jewelry from her uncle. The treasury was in artistic disarray, so she decided to put it in order. The jewelry consists of necklaces made of precious and rare gemstones, and no two of them are alike. Help Malgosia organize this valuable collection.

Write a program that:

reads the descriptions of the jewelry from standard input,
sorts them by increasing length, breaking ties among equal-length descriptions lexicographically,
prints the sorted strings to standard output.

Strings of equal length are ordered lexicographically: of two different strings of equal length, the smaller one is the string that has the smaller character at the first position where they differ.

Input

The first line contains the number of strings to analyze $N$ ( $N \le 150$ ). Each of the next $N$ lines contains the description of one piece of jewelry. Each description is a non-empty string of lowercase Latin letters ('a'..'z'), corresponding to the gemstones used, with length not exceeding $200$ characters.

Output

Print the strings in ascending order, one per line.

Examples5

Example 1

Input

5
aabaa
daz
ccc
dba
abzzbaz

Expected output

ccc
daz
dba
aabaa
abzzbaz

Example 2
Input
```
1
abc
```
Expected output
```
abc
```
Example 3
Input
```
3
z
ab
a
```
Expected output
```
a
z
ab
```

Example 4

Input

4
grapes
banana
apple
cherry

Expected output

apple
banana
cherry
grapes

Example 5
Input
```
3
abc
a
ab
```
Expected output
```
a
ab
abc
```