Stably sort non-negative integers by the sum of their decimal digits.

Input

The first line contains \(n\). The second line contains \(n\) non-negative integers.

The input satisfies:

• \(0 <= n <= 1000\)

Output

Print the sorted values separated by spaces. Values with equal digit sum retain their input order.

Example

Input

5
231 123 321 456 100

Output

100 321 231 123 456