Alien Dictionary

You are given a list of words sorted in lexicographical order according to an unknown alien language. Your task is to derive the order of characters in this alien language. If there is no valid ordering (i.e. the input is inconsistent) then output an empty string.

More formally, given a sequence of words, you need to determine a string of unique characters that represents the lexicographically smallest order of all the characters in the alien language such that for every two consecutive words w₁ and w₂, the first different character between them determines the ordering. If w₁ is longer than w₂ and w₁ starts with w₂, then the ordering is invalid.

In terms of constraints, if there exist multiple valid orders, you must return the lexicographically smallest one.

The ordering algorithm is based on the following idea:

• Construct a directed graph where each unique character is a vertex.
• For every two consecutive words, determine the first differing character and add a directed edge between them.
• If the input is found invalid (i.e. a prefix condition is violated), return an empty string.
• Perform a topological sort on the graph using a min-heap (priority queue) so that at each step the smallest available character is chosen.
</p>

inputFormat

The input is given on the standard input. The first line contains a single integer n (n ≥ 1), the number of words. Each of the following n lines contains one word consisting of lowercase English letters.

outputFormat

Output the lexicographically smallest valid ordering of characters as a single string. If no valid ordering exists, output an empty string.## sample

5
wrt
wrf
er
ett
rftt

wertf