A Problem for Alf

Interview

Time limit2sMemory limit1024 MB

Summary

Arrange the given non-negative integers in an order so that concatenating them produces the largest possible number.

Level: Medium5 of 10
Topics: Greedy, Sorting, String
Solved: No attempts yet

Problem

Willy Tanner gave Alf an interesting problem to keep him busy.

Alf has $n$ non-negative integers. Any number can be appended to the end of another number to form a new number. For example, from $123$ and $456$ you can get either $123456$ or $456123$ . The task is to join all the numbers into one so that the result is as large as possible. If Alf has the two numbers $123$ and $456$ , the answer is $456123$ .

Willy gave Alf a very large number of integers. The TV will not watch itself, so Alf asks you to write a program that solves the problem.

Input

The first line contains $n$ ( $1 \le n \le 10^5$ ), the number of integers Alf was given. The second line contains $n$ integers $a_i$ ( $0 \le a_i \le 10^9$ ), separated by spaces.

Output

Print the $n$ integers from the input, separated by spaces, in an order such that concatenating them in sequence gives the largest possible number.

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
3 2 1
```
Example 2
Input
```
4
20 17 18 2
```
Expected output
```
2 20 18 17
```