Problem Description

A list of words with an unknown dictionary order has been discovered. It contains $n$ words.

Although the specific dictionary order is unknown, it is known that the words are arranged in dictionary order.

You need to determine the dictionary order according to which this list of words is arranged.

Input Format

The first line of input contains an integer $n$, representing the number of words.

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

Output Format

Output a single line:

• If there is a unique dictionary order, output the letters in the order you determined.
• If no solution exists, output !.
• If there are multiple possible dictionary orders, output ?.

Sample Input and Output

Sample Input #1

5
ula
uka
klua
kula
al

Sample Output #1

luka

Sample Input #2

4
jaja
baba
baja
beba

Sample Output #2

!

Sample Input #3

3
marko
darko
zarko

Sample Output #3

?

Notes

Sample 1 Explanation

From the first column of letters, it is clear that the dictionary order of a, k, and u is u, k, a. Observing the second column, l comes before u. Therefore, the final dictionary order is luka, and it is the only solution.

Data Size and Constraints

For $100\%$ of the data, it is guaranteed that $1 \le n \le 100$, and all words contain only lowercase letters with at most $10$ characters.

Notes

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

见题面 Input 部分

见题面 Output 部分