Word Game

Time limit2sMemory limit2048 MB

Summary

Given up to 5 lowercase words, merge them pairwise by overlapping suffix and prefix to get the shortest possible single word, breaking ties lexicographically, or output -1 if impossible.

Level: Medium5 of 10
Topics: Brute force, String, String matching, Recursion
Solved: No attempts yet

Problem

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$ .

Examples3

Example 1
Input
```
2
aba
bab
```
Expected output
```
abab
```
Example 2
Input
```
3
ab
bc
ca
```
Expected output
```
abca
```
Example 3
Input
```
2
x
y
```
Expected output
```
-1
```