Nhập vào số nguyên dương \(n\) và dãy số nguyên \(a_1,a_2,…,a_n.\)

Yêu cầu: In ra dãy trên theo thứ tự tổng các chữ số của số trong dãy tăng dần, nếu có hai số có tổng chữ số bằng nhau, thì số nhỏ hơn sẽ in ra trước.

Input

• Dòng thứ nhất chứa số nguyên \(n(1≤n≤10^6 )\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n ( |a_i |≤10^{18} ).\)

Output

• In ra trên một dãy dãy sau khi đã sắp xếp thỏa mãn bài toán.

Sample Input

5
9999234 7593486749 9923499 9912399 1111122222

Sample Output

1111122222 9912399 9923499 9999234 7593486749