Zach is investigating patterns in a series of numbers, but needs them to be grouped in a particular ordering. He has already tried putting them in ascending order to no results. Next, he would like to try looking at the numbers in ascending order of the last digit only. In the case of ties, numbers should be in ascending order.

Input

The first line contains an integer ~n\ (1 \leq n \leq 10^6)~ representing the amount of numbers to be sorted.

The next line consists of ~n~ space separated integers ~x_i\ (0 \leq x_i \leq 10^9)~ which need to be sorted.

Output

Output a space separated list of the sorted numbers.

Example

Input 1

4
19 74 27 4

Output 1

4 74 27 19

Explanation 1

The final digits in order are 4, 4, 7, 9. 4 is less than 74 and so goes first to break the tie.

Input 2

5
356 388 1 479 453

Output 2

1 453 356 388 479