e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Digital root

Digital root

The digital root of a number n is defined next way: we take the sum of digits of n, then the sum of digits of obtained number and so on until we get one digit number.

You must sort the elements of array in increasing order of their digital roots. If the digital roots are equal, put first the less number.

Input

One line contains the array elements. The length of array is no more than 200, each number is positive and does not exceed 109.

Output

Print the elements of array sorted in increasing order of their digital roots.

Time limit 1 second
Memory limit 128 MiB
Input example #1
15 14 13 12 11 10 9 8 7
Output example #1
10 11 12 13 14 15 7 8 9
Input example #2
80 61 51 41 22 1
Output example #2
1 22 41 51 61 80