URI Online Judge | 2829

Uppercase, Why?

By Emilio Wuerges, UFFS BR Brazil

Timelimit: 1

The lexicon problem taught us how to sort 2 words. However, when the list of words was being built, the intern in charge made the mistake of including Uppercase characters!

Now we have a huge list of words, with both lowercase, from a to z, and uppercase characters, from A to Z!

We need to sort them, obeying the same order as before, regardless if the character is lowercase or uppercase.

However, the uppercase characters will be used to break ties, once all letters have been compared. In this case we consider that the uppercase character comes first.

Input

The first line contains an integer \(1 \leq N \leq 5 \times 10^4\).

Each of the following N lines contain a single word. Every word has at most 20 characters.

Output

The output must contain the list of words, sorted.

Input Samples Output Samples

4
Abcd
zbcd
zBce
abzd

Abcd
abzd
zbcd
zBce

5
Abc
abc
xyz
xYz
zzz

Abc
abc
xYz
xyz
zzz