Sắp tới lễ hội thể thao chào mừng ngày 26/3 của trường THCS Nhữ Bá Sỹ, Phúc muốn mua một đôi giày mới để tham gia thi đấu.

Phúc đã tham khảo được một danh sách các mức giá dự kiến (là các số nguyên không âm). Tuy nhiên, để dễ so sánh và lựa chọn, Phúc nghĩ ra một cách đánh giá đặc biệt:

• Giá trị của một số \(x\) được định nghĩa là tổng các chữ số của nó

Ví dụ:

• \(123 \rightarrow 1 + 2 + 3 = 6\)
• \(909 \rightarrow 9 + 0 + 9 = 18\)
• \(5 \rightarrow 5\)
• \(1000 \rightarrow 1 + 0 + 0 + 0 = 1\)

Phúc muốn sắp xếp lại danh sách giá theo quy tắc:

1. Giá trị tăng dần
2. Nếu hai số có cùng giá trị → số nhỏ hơn đứng trước

Hãy giúp Phúc sắp xếp lại danh sách này.

Input

• Dòng đầu tiên chứa số nguyên \(n\) — số lượng mức giá
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\)

Ràng buộc

• \(1 \le n \le 10^5\)
• \(0 \le a_i \le 10^9\)

Output

• In ra \(n\) số sau khi sắp xếp theo yêu cầu

Example

5
123 5 909 10 20

10 20 5 123 909

Chấm điểm

• Subtask 1 (30%): \(1 \le n \le 100\)
• Subtask 2 (70%): Không có ràng buộc thêm