Merge Words

Time limit5sMemory limit128 MB

Summary

Given up to 12 uppercase words, find the shortest string containing all of them as substrings, breaking ties by lexicographic order.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, String, String matching
Solved: No attempts yet

Problem

You are given N words consisting only of uppercase English letters. Print the shortest string that contains every given word as a substring.

Input

The first line contains the number of words N (1 <= N <= 12). Each of the next N lines contains one word consisting only of uppercase English letters. Each word has length at most 50.

Output

Print the answer on the first line. If there are multiple possible answers, print the lexicographically smallest one.

Examples6

Example 1
Input
```
2
BAB
ABA
```
Expected output
```
ABAB
```

Example 2

Input

4
ABABA
AKAKA
AKABAS
ABAKA

Expected output

ABABAKAKABAS

Example 3
Input
```
6
AAA
BBB
CCC
ABC
BCA
CAB
```
Expected output
```
AAABBBCABCCC
```
Example 4
Input
```
2
STRING
RING
```
Expected output
```
STRING
```

Example 5

Input

8
OFG
SDOFGJTILM
KBWNF
YAAPO
AWX
VSEAWX
DOFGJTIL
YAA

Expected output

KBWNFSDOFGJTILMVSEAWXYAAPO

Example 6

Input

8
NVCSKFLNVS
HUFSPMRI
FLNV
KMQD
RPJK
NVSQORP
UFSPMR
AIHUFSPMRI

Expected output

AIHUFSPMRINVCSKFLNVSQORPJKMQD