2451 - The Smallest String Concatenation

2451.The Smallest String Concatenation

Time Limit: 1s Memory Limit: 256MB

You're given a list of n strings a1,a2,...,an. 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 Format(From the terminal/stdin)

The first line contains integer n - the number of strings (1 \le n \le 5 \cdot 104).

Each of the next n lines contains one string ai (1 \le |ai| \le 50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5 \cdot 104.

Output Format(To the terminal/stdout)

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

Sample Input 1

Copy

4
abba
abacaba
bcd
er
 \n
    \n
       \n
   \n
  \n

Sample Output 1

Copy

abacabaabbabcder
                \n

Sample Input 2

Copy

5
x
xx
xxa
xxaa
xxaaa
 \n
 \n
  \n
   \n
    \n
     \n

Sample Output 2

Copy

xxaaaxxaaxxaxxx
               \n

Sample Input 3

Copy

3
c
cb
cba
 \n
 \n
  \n
   \n

Sample Output 3

Copy

cbacbc
      \n

Submit

请先登录

Submit

题解(0)