An alien language uses the lowercase English letters but in an unknown alphabetical order. You are given a list of words that is sorted according to that alien order. Work out an ordering of the letters that is consistent with the list. If several orderings are possible, print the lexicographically smallest one (by normal English order). Include every letter that appears in the words. If no ordering is consistent, print invalid.
Input
Line 1: n, the number of words. Line 2: the n words separated by spaces, in the alien sorted order.
Output
Print the letters in the alien order as one string, or invalid.
Constraints
1 <= n <= 100 1 <= length of each word <= 100
5 wrt wrf er ett rftt
wertf
The rules give t < f, w < e, r < t and e < r, so the order is wertf.
2 abc ab
invalid
A longer word cannot come before its own prefix.