String Decoration

Time limit1sMemory limit128 MB

Summary

Given N words that can each be cut into ordered pieces and interleaved freely, find the lexicographically smallest concatenation of all pieces.

Level: Medium6 of 10
Topics: Greedy, String, Sorting
Solved: No attempts yet

Problem

Minsik wants to make one string W from N given words.

He may first split each word into any number of pieces. Then he concatenates all pieces to make W. The pieces that came from the same word must keep their original order in that word.

For instance, suppose he has the three words {YOUNGSIK, DONGHO, ALGORITHM}. He could split them into pieces such as {YOUNG, SIK, DO, NG, HO, AL, GO, RITHM}, then concatenate the pieces as shown below.

YOUNG     SIK
     DO      NG    HO
       AL      GO    RITHM
--------------------------
YOUNGDOALSIKNGGOHORITHM

Print the lexicographically smallest string that Minsik can make.

Input

The first line contains the number of words N. N is at most 20.

Each of the next N lines contains one word. Each word has length at most 1,000 and consists only of uppercase English letters, with no spaces.

Output

Print the lexicographically smallest string that can be made.

Examples5

Example 1
Input
```
4
CCCA
CCCB
CCCD
CCCE
```
Expected output
```
CCCACCCBCCCCCCDE
```

Example 2

Input

5
KOOSAGA
XIAOWUC
DOTORYA
CKI
THENITROMEFAN

Expected output

CDKIKOOOSAGATHENITORTROMEFANXIAOWUCYA

Example 3

Input

5
BKSDSOPTDD
DDODEVNKL
XX
PODEEE
LQQWRT

Expected output

BDDKLODEPODEEEQQSDSOPTDDVNKLWRTXX

Example 4

Input

5
QITHSQARQV
BYLHVGMLRY
LKMAQTJEAM
AQYICVNIKK
HKGZZFFEWC

Expected output

ABHKGLKMAQIQQTHSQARQTJEAMVYICVNIKKYLHVGMLRYZZFFEWC

Example 5

Input

5
XHCYBTUQUW
EKBISADSSN
LOOISPOFAK
MIXBDHPJUQ
BNMNDHMOTC

Expected output

BEKBILMINMNDHMOOIOSADSPOFAKSSNTCXBDHPJUQXHCYBTUQUW