**9 人解决**，11 人已尝试。

**11 份提交通过**，共有 31 份提交。

**5.8** EMB 奖励。

**单点时限: **2.0 sec

**内存限制: **512 MB

Consider $n$ given non-empty strings denoted by $s_1, s_2, \ldots, s_n$. Now for each of them, you need to select a corresponding suffix, denoted by $suf_1, suf_2, \ldots, suf_n$. For each string $s_i$, the suffix $suf_i$ is a non-empty substring whose right endpoint is the endpoint of the entire string. For instance, all suffixes of the string “jiangsu” are “u”, “su”, “gsu”, “ngsu”, “angsu”, “iangsu” and itself.

All selected suffixes could assemble into a long string $T = suf_1, suf_2, \ldots, suf_n$. Here plus signs indicate additions of strings placing the latter at the tail of the former. your selections of suffixes would determine the lexicographical order of $T$.

Now, your mission is to find the one with minimum lexicographical order.

Here is a hint about lexicographical order. To compare strings of different lengths, the shorter string is usually padded at the end with enough “blanks” which is a special symbol that is treated as smaller than every letters.

The first line contains an positive interger $n$ ($1 \le n \le 500~000$). Each of the following $n$ lines contains a string entirely in lowercase, corresponding to $s_1, s_2, \ldots, s_n$. The summation of lengths of all strings in input is smaller or equal to $500~000$.

Output the string $T$ with minimum lexicographical order.

Input

2 abababbaabbababba abbabbabbbababbab

Output

aab

Input

3 aba aab bab

Output

aaabab

Input

3 bbb aaa ccc

Output

baaac

**9 人解决**，11 人已尝试。

**11 份提交通过**，共有 31 份提交。

**5.8** EMB 奖励。

题目标签