C. The Smallest String Concatenation

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

Output

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

Examples

input

4
abba
abacaba
bcd
er

output

abacabaabbabcder

input

5
x
xx
xxa
xxaa
xxaaa

output

xxaaaxxaaxxaxxx

input

3
c
cb
cba

output

cbacbc

       EDITORIAL

The problem was suggested by Lewin Gan lewin. The proof of the transitivity also belongs to him.

Let's sort all the strings by comparator a + b < b + a and concatenate them. Let's prove that it's the optimal answer. Let that operator be transitive (so if ). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer.

Let's prove the transitivity of operator. Consider the strings as the 26-base numbers. Then the relation a + b < b + a equivalent to . The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.

C++ solution by me.

Python solution by lewin.

Complexity: O(nLlogn), where L is the maximal string length.

  *********************** CODE GOES HERE********************

#include<bits/stdc++.h>

using namespace std;

#define ll long long int 

int a[500010];

#define mxn 500010

ll fa[mxn];

ll fb[mxn];

ll bb[mxn];

ll ba[mxn];

int bob[mxn];

#define pb push_back

bool cmp(string a ,string b)

{

  return a+b<b+a;

}

int main()

{

    int n;

    cin>>n;

    vector<string> v;

    for(int i=0;i<n;i++)

    {

      string s;

      cin>>s;

      v.pb(s);

}

sort(v.begin(),v.end(),cmp);

for(int i=0;i<n;i++)

cout<<v[i];

cout<<endl;

return 0;

}