Group Word Reconstruction

Time limit2sMemory limit128 MB

Summary

Reconstruct the unique group word, where every letter forms one contiguous block, by arranging all given unordered pieces, or report impossibility or multiple solutions.

Level: Medium7 of 10
Topics: Graph, String, DFS, Greedy
Solved: No attempts yet

Problem

A word is a group word if, for every lowercase letter, all occurrences of that letter form one contiguous block. For example, aabbbcc is a group word, while abca is not because the letter a is split into two blocks.

One group word was cut into several pieces, and the pieces are given in arbitrary order. Use every piece exactly once and find the original group word that can be reconstructed.

Input

The first line contains the number of pieces N. N is a positive integer not greater than 50.

Each of the next N lines contains one piece. Each piece is a lowercase English string of length at most 20.

Output

If exactly one original group word is possible, output that word.

If multiple words are possible, output -_-. If no ordering can make a group word, output gg.

Examples6

Example 1
Input
```
2
te
st
```
Expected output
```
stte
```
Example 2
Input
```
3
aaa
a
aa
```
Expected output
```
aaaaaa
```
Example 3
Input
```
2
ab
bba
```
Expected output
```
gg
```
Example 4
Input
```
3
te
s
t
```
Expected output
```
-_-
```
Example 5
Input
```
4
orr
rd
woo
www
```
Expected output
```
wwwwooorrrd
```
Example 6
Input
```
1
abcb
```
Expected output
```
gg
```