You are given a list of N distinct words.
Find the longest word in the list that can be obtained by concatenating other words from the list. Any word can be used multiple times in the concatenation.
Input
The first line of input contains an integer N.
Each of the following N lines contains a word.
Output
The only line of output should contain the longest word with the required property, or -1 if no such word exists.
Constraints
- 1 ≤ N ≤ 100
- Each word contains at most 100 lowercase letters from the English alphabet.
- If a solution exists, it is guaranteed to be unique.
Samples
| Input | Output |
|---|---|
| 6 berry cat strawberry str snake aw | strawberry |
| 8 sensual o b movimiento mba un boooooooooooooooooooooooooooomba unmovimientosensual | boooooooooooooooooooooooooooomba |
| 3 happy birthday mike | -1 |
