Sorting by weights— Community Task

Given an array of integers. Sort it in ascending order by the sum of the digits of each number (the weight of the number). If two numbers have the same sum of digits, they should be sorted in ascending order of the numbers themselves. Output the sorted array.

Input Format

In the first line, an integer N (1 ≤ N ≤ 1000) — the number of values. In the second line, N integers, each with an absolute value not exceeding 10^6.

Output Format

Output N numbers — the sorted array.

Examples

Example 1

INPUT

5
12 3 21 10 5

OUTPUT

10 3 12 21 5

Example 2

INPUT

OUTPUT

1 2 3

Example 3

INPUT

3
100 1 10

OUTPUT

1 10 100

Example 4

INPUT

1 10

OUTPUT

10

Example 5

INPUT

4
apple banana cherry apple
3
banana date fig

OUTPUT

apple banana cherry date fig