Description

Given $n$ strings $(S_1, S_2, \dots, S_n)$, find the shortest string $T$ such that all $n$ strings $(S_1, S_2, \dots, S_n)$ are substrings of $T$.

Input Format

The first line contains an integer $n$, the number of given strings. The next $n$ lines each contain a string consisting only of uppercase letters.

Output Format

Output a single line containing the shortest string $T$. Among all shortest candidates, if there are multiple strings that satisfy the requirement, output the lexicographically smallest one.

2
ABCD
BCDABC

ABCDABC

Hint

For $100\%$ of the testdata, $n \leq 12$, and the length of each string does not exceed $50$.

Translated by ChatGPT 5