You're given a list of n strings a_1, a_2, ..., 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^4).

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^4.


-----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

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

from functools import cmp_to_key
def cmpEqLen(a, b):
    if a < b:
        return -1
    elif a > b:
        return 1
    else:
        return 0

def compare(a, b):
    alen = len(a)
    blen = len(b)
    if alen == blen:
        return cmpEqLen(a, b)
    l = min(alen, blen)
    c = cmpEqLen(a[:l], b[:l])
    if c != 0:
        return c

    if alen > blen:
        return -compare(a[:l], a[l:])
    else:
        return compare(b[:l], b[l:])

N = int(input())
arr = [input() for _ in range(N)]
arr.sort(key=cmp_to_key(compare))
print(''.join(arr))


def mergesort(s):
    if len(s) == 1:
        return s
    s1 = mergesort(s[:len(s) // 2])
    s2 = mergesort(s[len(s) // 2:])
    return merge(s1, s2)


def merge(s1, s2):
    f = []
    ind1 = 0
    ind2 = 0
    while ind1 != len(s1) and ind2 != len(s2):
        if str(s1[ind1]) + str(s2[ind2]) > str(s2[ind2]) + str(s1[ind1]):
            f.append(s2[ind2])
            ind2 += 1
        else:
            f.append(s1[ind1])
            ind1 += 1
    if ind1 != len(s1):
        f.extend(s1[ind1:])
    else:
        f.extend(s2[ind2:])
    return f


n = int(input())
s = []
for i in range(n):
    s.append(input())
print(''.join(mergesort(s)))

def mergesort(s):
    if len(s) == 1:
        return s
    s1 = mergesort(s[:len(s) // 2])
    s2 = mergesort(s[len(s) // 2:])
    return merge(s1, s2)


def merge(s1, s2):
    f = []
    ind1 = 0
    ind2 = 0
    while ind1 != len(s1) and ind2 != len(s2):
        if str(s1[ind1]) + str(s2[ind2]) > str(s2[ind2]) + str(s1[ind1]):
            f.append(s2[ind2])
            ind2 += 1
        else:
            f.append(s1[ind1])
            ind1 += 1
    if ind1 != len(s1):
        f.extend(s1[ind1:])
    else:
        f.extend(s2[ind2:])
    return f


n = int(input())
s = []
for i in range(n):
    s.append(input())
print(''.join(mergesort(s)))

from functools import cmp_to_key
import locale
def cmp(s, t):
    if s+t < t+s: return -1
    if s+t > t+s: return  1
    return 0

n = int(input())
S = [input() for i in range(n)]
S.sort(key = cmp_to_key(cmp))
print(''.join(S))


n = int(input())
A = []
for i in range(n):
    A.append(input())
def custom_sort(s1,s2):
    n1 = len(s1)
    n2 = len(s2)
    if n1 == n2:
        if s1 <= s2:
            return -1
        else:
            return 1
    else:
        if (s1+s2) <= (s2+s1):
            return -1
        else:
            return 1

import functools
A.sort(key=functools.cmp_to_key(custom_sort))
print("".join(A))


n = int(input())
A = []
for i in range(n):
    A.append(input())
def custom_sort(s1,s2):
    if (s1+s2) <= (s2+s1):
        return -1
    else:
        return 1

import functools
A.sort(key=functools.cmp_to_key(custom_sort))
print("".join(A))

from functools import cmp_to_key

def f(x, y):
    return -1 if x + y < y + x else 1

n = int(input())
A = []
for i in range(n):
    s = input()
    A.append(s)
print(''.join(sorted(A, key = cmp_to_key(f))))

def compare(f, u):
    if f + u < u + f:
        return -1
    elif f + u == u + f:
        return 0
    else:
        return 1
    

from functools import cmp_to_key
n = int(input())
s = []
for i in range(n):
    s.append(input())
print(''.join(sorted(s, key = cmp_to_key(compare))))

def mergesort(s):
    if len(s) == 1:
        return s
    s1 = mergesort(s[:len(s) // 2])
    s2 = mergesort(s[len(s) // 2:])
    return merge(s1, s2)


def merge(s1, s2):
    f = []
    ind1 = 0
    ind2 = 0
    while ind1 != len(s1) and ind2 != len(s2):
        if str(s1[ind1]) + str(s2[ind2]) > str(s2[ind2]) + str(s1[ind1]):
            f.append(s2[ind2])
            ind2 += 1
        else:
            f.append(s1[ind1])
            ind1 += 1
    if ind1 != len(s1):
        f.extend(s1[ind1:])
    else:
        f.extend(s2[ind2:])
    return f


n = int(input())
s = []
for i in range(n):
    s.append(input())
print(''.join(mergesort(s)))

def mergesort(s):
    if len(s) == 1:
        return s
    s1 = mergesort(s[:len(s) // 2])
    s2 = mergesort(s[len(s) // 2:])
    return merge(s1, s2)


def merge(s1, s2):
    f = []
    ind1 = 0
    ind2 = 0
    while ind1 != len(s1) and ind2 != len(s2):
        if str(s1[ind1]) + str(s2[ind2]) > str(s2[ind2]) + str(s1[ind1]):
            f.append(s2[ind2])
            ind2 += 1
        else:
            f.append(s1[ind1])
            ind1 += 1
    if ind1 != len(s1):
        f.extend(s1[ind1:])
    else:
        f.extend(s2[ind2:])
    return f


n = int(input())
s = []
for i in range(n):
    s.append(input())
print(''.join(mergesort(s)))
#+


import functools
import math
import sys

#n, p = map(int, input().split())
def cmp(x, y):
    if x < y:
        return -1
    elif x > y:
        return 1
    else:
        return 0
    
print(("".join(sorted([s.rstrip() for s in sys.stdin.readlines()[1:]], \
key=functools.cmp_to_key(lambda x,y: cmp(x + y, y + x))))))


from functools import cmp_to_key

def cmp(a,b):
	x=a+b
	y=b+a
	if x<y: return -1
	elif x==y: return 0
	return 1

n,a = int(input()),[]
for i in range(n): a.append(input())
a.sort(key=cmp_to_key(cmp))
for i in a:
	print(i,end='')

from functools import cmp_to_key
print(''.join((sorted((input() for _ in range(int(input()))), key=cmp_to_key(lambda a, b: 1 if a + b > b + a else-1)))))

from functools import cmp_to_key

n = int(input())
strings = [input() for i in range(n)]

"""
def cmp(s1, s2):
    l = min(len(s1), len(s2))
    for i in range(l):
        if s1[i] < s2[i]:
            return -1
        elif s1[i] > s2[i]:
            return 1
    if len(s1) < len(s2):
        return ord(s1[0]) - ord(s2[l])
    elif len(s1) > len(s2):
        return ord(s1[l]) - ord(s2[0])
    return 0
"""

def cmp(s1, s2):
    z1, z2 = s1 + s2, s2 + s1
    if z1 < z2:
        return -1
    elif z2 > z1:
        return 1
    else:
        return 0

strings.sort(key=cmp_to_key(cmp))
for string in strings:
    print(string, end="")
print("")

from functools import cmp_to_key

def compare(x, y):
    if y+x < x+y:
        return -1
    if x+y < y+x:
        return 1
    if x+y == y+x:
        return 0

n = int(input())
s = []
for i in range(n):
    a = input()
    s.append(a)
r = sorted(s, key=cmp_to_key(compare), reverse=True)
for i in range(n):
    print(r[i], end="")


from functools import cmp_to_key
n = int(input())
S = []
for i in range(n):
    S.append(input())
S.sort(key = cmp_to_key(lambda x,y : 1 if x+y > y+x else -1))
print(''.join(S))

# -*- coding: utf-8 -*-
"""
Created on Thu Apr 14 15:41:54 2016

@author: kebl4230

Too slow. Possibly lots of unnecessary list manipulation.
"""
from functools import cmp_to_key
n = int(input())
strings = list()
for i in range(n):
    strings.append(input())


def cmpfunc(x, y):
    a = x + y
    b = y + x
    if a < b:
        return -1
    elif a == b:
        return 0
    else:
        return 1

bb = sorted(strings, key=cmp_to_key(cmpfunc))
print("".join(bb))


"""
n = int(input())
strings = list()
for i in range(n):
    strings.append(input())

aa = "abcdefghijklmnopqrstuvwxyz"
positions = [strings.copy()]


def myfunc(mylist, index, pos):
    scores = [aa.find(bb[index]) if index < len(bb) else 27 for bb in mylist]
    r = 0
    mins = min(scores)
    while mins <= 27:
        if r == 0:
            for i in range(len(scores)):
                if scores[i] == mins:
                    scores[i] = 100
        else:
            group = [mylist[n] for n in range(len(scores)) if scores[n] == mins]
            positions.insert(pos + r, group)
            for string in group:
                mylist.remove(string)
            while any(s == mins for s in scores):
                scores.remove(mins)
        r += 1
        mins = min(scores)

index = 0
maxlen = len(positions)
pos = 0
while any(len(pos) > 1 for pos in positions):
    myfunc(positions[pos], index, pos)
    pos += 1
    if pos == maxlen:
        pos = 0
        maxlen = len(positions)
        index += 1

result = ''
for aa in positions:
    result += aa[0]
print(result)
"""

def main():
	n = int(input())
	strings = [None] * n
	for i in range(n):
		strings[i] = input()
	print(solver(strings))

def solver(L):
	L.sort(key = cmp_to_key(customCompare))
	return ''.join(L)

def customCompare(x, y):
	a = x + y
	b = y + x
	if a < b:
		return -1
	elif a == b:
		return 0
	else:
		return 1
	# if len(x) == len(y):
	# 	return compareStrings(x, y)
	# elif isPrefix(x, y):
	# 	return compareStrings(x, y[len(x):])
	# elif isPrefix(y, x):
	# 	return compareStrings(x[len(y):], y)
	# else:
	# 	return compareStrings(x, y)

def compareStrings(x, y):
	if x < y:
		return -1
	elif x == y:
		return 0
	else:
		return 1

def isPrefix(s, t):
	if s == t[:len(s)]:
		return True

def cmp_to_key(mycmp):
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

# L = ["abba", "abacaba", "bcd", "er"]
# print(solver(L))

# L2 = ['x', 'xx', 'xxa', 'xxaa', 'xxaaa']
# print(solver(L2))

# L3 = ['c', 'cb', 'cba']
# print(solver(L3))

main()

from functools import cmp_to_key
n = int(input())
a=[]
for i in range(n):
    a.append(input())
def cmp(x,y):
    if x+y < y+x :
           return -1
    elif x+y > y+x:
           return 1
    else:
           return 0
print(''.join(sorted(a,key=cmp_to_key(cmp))))
#print(a.sort(key = lambda x,y: cmp(x,y)))


__author__ = 'Utena'
from functools import cmp_to_key
n=int(input())
s=[]
for i in range(n):
    s.append(input())
def cmp(x,y):
    if x+y<y+x:return -1
    else:return 1
s=sorted(s,key=cmp_to_key(cmp))
print(''.join(s))

from functools import cmp_to_key
n = int(input())
a = []
for i in range(n):
    a.append(input())
a.sort(key = cmp_to_key(lambda x,y : 1 if x+y > y+x else -1))
print(''.join(a))

from functools import cmp_to_key
a = []
n = int(input())
for i in range(n):
    a.append(input())
a.sort(key = cmp_to_key(lambda x,y : 1 if x+y > y+x else -1))
print(''.join(a))

from functools import cmp_to_key as ctk
s=[]
for o in range(int(input())):
    s+=[input()]
s.sort(key=ctk(lambda x,y:1 if x+y>y+x else -1))
print(''.join(s))


from functools import cmp_to_key
n = int(input())
l = []
for i in range(n):
    l.append(input())
    
l.sort(key = cmp_to_key(lambda x,y : 1 if x+y > y+x else -1))
print(''.join(l))

from sys import stdin
from functools import cmp_to_key
def input() :
    return stdin.readline()
def mysort(x,y) :
    return 1 if x+y>y+x else -1
n=int(input())
strings=[]
for i in range(n) :
    t=input().strip('\n')
    strings.append(t)
strings.sort(key=cmp_to_key(mysort))
print("".join(strings))