Minimizing Carry Operations

Prof. Pang is given (n) numbers (a_1, \ldots, a_n). He finds it easy to add these numbers with a computer, but he treasures his computer so much that he wants to reduce its workload. Instead, he decides to simulate the following program by hand: [ \texttt{s = 0;}] [ for\ i = 1\ to\ n:\quad s = s + a[i]]

Unlike a computer, the time required for Prof. Pang to simulate the program is proportional to the total number of carry operations that occur when calculating (s + a[i]) for each (i) using column addition in base-ten – the same method taught in primary school. A carry is generated in a column when the sum of the digits (plus any carry from the previous column) is at least 10. For example, when adding 56 and 67, a carry is produced in the ones place as (6+7 = 13) and again in the tens place due to the propagated carry.

Your task is to permute the array (a_1, \ldots, a_n) so that the total number of carry operations over the simulation is minimized. (By "permute an array", we mean that you can rearrange the elements arbitrarily.) A greedy strategy, such as sorting the array in non-decreasing order, will keep the running sum as small as possible and thereby help minimize the number of carries.

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 10^5)), representing the number of numbers. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n). All numbers are non-negative and do not exceed (10^9).

outputFormat

Output a permutation of the array that minimizes the total number of carry operations in the simulation. Print the numbers in one line separated by a single space.

sample

3
1 10 19

1 10 19