It is a little known fact that the cows love word games. They have their own cow crossword puzzles, cow word-find grids, and all sorts of other cow word games.

The cows need some computer assistance, though, in order to design certain word games. They have lists of $N$ distinct words ($2 \le N \le 20{,}000$) no longer than 100 characters, all of which are lower-case and contain only the letters 'a'..'z'.

They need to find two words in the list that share the longest prefix (i.e., the first $C$ characters of the words match and $C$ is the longest length for all possible pairs of words). The input datasets are guaranteed to have at least one pair of words with a shared prefix.

If more than two word pairs share prefixes of the same maximal size, the cows want to see the pair whose first word is closest to the beginning of the supplied list and whose other maximal-prefix word is closest to the beginning of the list.

Input

• Line $1$: One line with a single integer: $N$
• Lines $2..N+1$: Each line contains a single word.

Output

Two lines, each with a single word.

Examples

Input 1

9
noon
is
lunch
for
most
noone
waits
until
two

Output 1

noon
noone

Problem credits: Dan Adkins, 2001