Alien Dictionary Order

You are given a sorted list of words in an alien language. The words are sorted lexicographically according to the rules of this unknown language. Your task is to deduce the order of characters in this alien language.

The order of characters is defined by comparing adjacent words in the list. If a letter from one word differs from the letter at the same position in the next word, then the letter from the first word must come before the letter from the second in the alien dictionary. In the case that a word is a prefix of the next word, the order remains valid. If no valid order exists (e.g., due to a cycle or an invalid prefix condition), output an empty string.

Note: If there are multiple valid orders, any one of them is acceptable.

Mathematically, if we establish the relation \( a \prec b \) based on the first differing letter between two adjacent words, then the overall character order must be a topological ordering of the induced directed graph \( (V, E) \) where \( V \) is the set of all unique characters and \( E \) is the set \( \{ (a, b) \mid a \prec b \} \).

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \( n \) representing the number of words. The following \( n \) lines each contain one word from the alien language.

outputFormat

Output a single line to standard output (stdout) containing a string that represents the deduced order of characters. If no valid order exists, output an empty string.

5
baa
abcd
abca
cab
cad

bdac