Description

People have found a list of words whose alphabetical order is unknown. The list contains $n$ words.

Although the exact alphabetical order is unknown, it is known that these words are arranged in the list in alphabetical order.

You need to determine which alphabetical order this word list follows.

Input Format

The first line contains an integer $n$, which represents the number of words.

The next $n$ lines each contain a string describing a word.

Output Format

Output one line:

• If there is a unique alphabetical order, output the letters in order according to the order you found;
• If no answer exists, output !;
• If multiple alphabetical orders are possible, output ?.

5
ula
uka
klua
kula
al

luka

4
jaja
baba
baja
beba

!

3
marko
darko
zarko

?

Hint

Explanation for Sample 1

From the letters in the first column, we can know that the order of the three letters a k u is u k a. Then by looking at the second column, we can see that l comes before u. Therefore, the final alphabetical order is luka, and it is the only solution.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 100$. All words contain only lowercase letters and have length at most $10$.

Note

This problem is translated from COCI2010-2011 CONTEST #6 T4 ABECEDA。

Translated by ChatGPT 5