Problem M
Word Game
On the Word Game show, Ashley has selected $n$ words and asks Brandon to combine them. Two words $s$ and $t$ can be combined if $s$ has a suffix of length $k > 0$ that is a prefix of $t$. The result of combining them is a new word made of $s$ concatenated with the last $|t|-k$ letters of $t$. If there are multiple values of $k$ that are valid, any can be chosen.
Brandon must repeatedly take a pair of words from the list of words that can be combined, and replace them in the list with the combined word, until the list contains only a single word, and that word is as short as possible. If multiple final words of the same length are possible, Brandon must find the lexicographically first one.
Input
The first line of the input contains a single integer $n$ $(1 \le n \le 5)$, the number of words to start out with.
The next $n$ lines each contain a single word in lowercase letters of length at most 5.
Output
Output the lexicographically first word of minimum length Brandon can come up with. If it is not possible to come up with a single word, output $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 aba bab |
abab |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 ab bc ca |
abca |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 x y |
-1 |
