Longest Word

Given a list of words, find the longest word in the list that can be built one character at a time by other words in the list. In other words, for a word to be valid, every prefix of the word (from length 1 to length(word)-1) must also be present in the list. If there is more than one possible answer, return the lexicographically smallest one. If no such word exists, return an empty string.

Note: The input is provided from standard input (stdin) and the output should be printed to standard output (stdout).

Example:

Input:
6
w wo wor worl world banana
Output:
world

</p>

inputFormat

The first line contains an integer n indicating the number of words. The second line contains n space-separated words. Each word consists of lowercase English letters.

Example:

6
w wo wor worl world banana

outputFormat

Print the longest valid word according to the rules described. If more than one word qualifies, print the lexicographically smallest one. If no valid word exists, print an empty string.

## sample

6
w wo wor worl world banana

world