Interesting Sorting

You are given an array of N natural numbers. Your task is to sort this array in ascending order based on the sum of the digits of each number. If two numbers have the same digit sum, sort them in descending order by their value.

Input

The first line contains the integer n ($1$ ≤ $n$ ≤ $10^6$), representing the number of natural numbers. The following n lines each contain one natural number, with each number not exceeding $10^9$.

Output

Print the sequence of numbers sorted according to the specified conditions.

Examples