The Smallest String Concatenation

3000ms

262144K

Description:

You're given a list of n strings a₁, a₂, ..., a_n. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.

Given the list of strings, output the lexicographically smallest concatenation.

Input:

The first line contains integer n — the number of strings (1 ≤ n ≤ 5·10⁴).

Each of the next n lines contains one string a_i (1 ≤ |a_i| ≤ 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·10⁴.

Output:

Print the only string a — the lexicographically smallest string concatenation.

Sample Input:

4
abba
abacaba
bcd
er

Sample Output:

abacabaabbabcder

Sample Input:

5
x
xx
xxa
xxaa
xxaaa

Sample Output:

xxaaaxxaaxxaxxx

Sample Input:

3
c
cb
cba

Sample Output:

cbacbc

Informação

Provedor Codeforces

Código CF632C