Lexicographically Smallest Concatenation

You are given an array of non-negative integers. Your task is to rearrange the elements of the array such that when they are concatenated, they form the lexicographically smallest possible string.

More formally, given an array of integers \(A = [a_1,a_2,\dots,a_n]\), convert each integer to its string representation and then find a permutation \(P\) of these strings such that the concatenated string \[ S = s_{P(1)} + s_{P(2)} + \dots + s_{P(n)} \] is lexicographically minimum. If the array is empty, the output should be an empty string.

Note: In lexicographical order, string \(x\) is said to be smaller than string \(y\) if \(x\) is a prefix of \(y\) or if at the first position where \(x\) and \(y\) differ, the character in \(x\) comes before the character in \(y\) in alphabetical order. In our context, when comparing two strings \(a\) and \(b\), we compare \(a+b\) with \(b+a\) to decide the order.

inputFormat

The input is provided via standard input (stdin) and has the following format:

n
num1 num2 ... numn

Here, n is an integer representing the number of elements in the array. The next line contains n space-separated non-negative integers.

outputFormat

Output a single line containing the lexicographically smallest concatenated string formed by all elements in the array.

3
56 9 5

5569