Short message 4

Interview

Time limit1sMemory limit1024 MB

Summary

Build the shortest lowercase string that contains every given planet name as a substring.

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

Problem

The Space Exploration Center has identified $N$ planets, each with a name $S_i$ made up only of lowercase Latin letters. The center's researchers believe that if any of these planets has intelligent life, its inhabitants will reply to a message that contains the planet's name.

Sending cosmic messages is expensive, so the goal is to build a message as short as possible that contains the names of all $N$ planets as substrings.

A string $s$ is a substring of a string $t$ if $s$ can be obtained from $t$ by deleting some characters from the beginning and the end of $t$ .

Input

The first line contains the number of planets $N$ . Each of the next $N$ lines contains one planet name $S_i$ .

Output

Print one line containing a message made up only of lowercase Latin letters. The message must contain every planet name from the input as a substring.

Examples1

Example 1
Input
```
4
aba
ac
ba
caab
```
Expected output
```
abaaccaaba
```