You are given a dictionary of words sorted according to the rules of an unknown alien language.

Using the sorted dictionary, determine a valid ordering of the alien alphabet.

If multiple valid orderings exist, return the lexicographically smallest valid ordering.

If the dictionary is invalid (contains a contradiction), print:

INVALID

A contradiction occurs when:

• A cycle exists in the character dependencies.
• A longer word appears before its own prefix.

---

Input Format

• The first line contains an integer N, representing the number of words.
• The second line contains N space-separated words representing the dictionary order.

---

Output Format

Print:

• A string representing the lexicographically smallest valid character ordering, or
• INVALID if no valid ordering exists.

---

Constraints

• 1 ≤ N ≤ 10^5
• Total number of characters across all words ≤ 10^5

---

Sample Input

5
baa abcd abca cab cad

Sample Output

bdac

---

Explanation

From the given dictionary:

• baa → abcd gives b < a
• abcd → abca gives d < a
• abca → cab gives a < c
• cab → cad gives b < d

These constraints produce the ordering:

b < d < a < c

Hence, the lexicographically smallest valid ordering is:

bdac

If a cycle exists or a word appears before its own prefix (e.g., abcd before ab), the output should be:

INVALID

---