You are given n non-negative integers. Arrange all of them in some order and concatenate their decimal representations into a single number. Among every possible arrangement, print the one that yields the largest number.
Because different orderings can never produce two different largest strings, the answer is unique. Print it as a canonical decimal string with no leading zeros; if the largest possible number is zero (which happens exactly when every input is 0), print a single 0.
The key idea: for two tokens a and b, a should come before b when the string a+b is greater than the string b+a (comparing the two concatenations as strings).
Input format
Line 1: an integer n — the count of numbers.
Line 2: n space-separated non-negative integers, each given without leading zeros (the token for zero is exactly 0).
Output format
A single line: the largest number formed by concatenating all tokens, as a canonical string (no leading zeros, except the value zero which is printed as 0).
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ each value ≤ 1000000000
- Each token has no leading zeros (the zero value is the single character
0).