Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language. If the order is invalid, return "". If there are multiple valid orderings, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller only if s.length < t.length.

Examples

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]

Output: "wertf"

Explanation: From the words we can derive: w comes before e, e before r, t before f, r before t. This gives the order "wertf".

Example 2:

Input: words = ["z","x"]

Output: "zx"

Explanation: From the dictionary order, z comes before x.

Example 3:

Input: words = ["z","x","z"]

Output: ""

Explanation: The order is invalid because z appears both before and after x.

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of only lowercase English letters