Alien Dictionary Order

In an alien language, the order of the alphabet is unknown. Given a sorted dictionary of the alien language consisting of n words, your task is to determine the lexicographically smallest valid order of characters. The order is determined by comparing adjacent words and deducing the relative order between different characters. If no valid order exists (for instance, if a word is a prefix of a previous word or if there is a cycle in the dependency of characters), output an empty string.

Note: In case there are multiple valid orders, you must output the lexicographically smallest one (i.e., the one that comes first in dictionary order).

inputFormat

The first line of input contains an integer n (0 ≤ n ≤ 10^5), representing the number of words in the alien dictionary. Each of the following n lines contains a non-empty string made up of lowercase letters, representing a single word from the dictionary. It is guaranteed that the total length of all words does not exceed 10^6.

outputFormat

Print a single string representing the lexicographically smallest valid order of characters in the alien language. If no valid order can be determined, print an empty string.## sample

5
wrt
wrf
er
ett
rftt

wertf