Word Sorting

Interview

Time limit2sMemory limit256 MB

Summary
Deduplicate a list of words and sort them first by length, then lexicographically.
Level

Easy2 of 10

Topics
Sorting, String
Solved
No attempts yet

Problem

You are given N lowercase English words. Remove duplicate words, then sort the remaining words by the following rules.

  1. A shorter word comes first.
  2. If two words have the same length, the lexicographically smaller word comes first.

Input

The first line contains the number of words N. (1 ≤ N ≤ 20,000)

Each of the next N lines contains one lowercase English word. The length of each word is at most 50.

Output

Print the unique words in the required order, one word per line.

Examples1

  1. Example 1

    Input
    13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours
    Expected output
    i
im
it
no
but
more
wait
wont
yours
cannot
hesitate