Alien Dictionary

An alien language uses the lower-case letters in an unknown alphabetical order. words is a list of words sorted in that language's order. Return a string with every letter that appears in the words, in an order that is consistent with the list. If several orders fit, return the lexicographically smallest (in normal English order). If no order fits (a contradiction, or a longer word placed before its own prefix), return "".

For ["wrt", "wrf", "er", "ett", "rftt"] the answer is "wertf".

Examples

Example 1

Input:

alien_order(['wrt', 'wrf', 'er', 'ett', 'rftt'])

Output:

'wertf'

Example 2

Input:

alien_order(['abc', 'ab'])

Output:

''

Constraints

• 0 <= len(words) <= 10000
• 1 <= len(word) <= 20, lower-case letters.