Tại hội chợ ngày 26/3 của trường THCS Nhữ Bá Sỹ, nhóm bạn gồm Phúc, Khoa, Mạnh, Bảo Linh đang quản lý một gian hàng bán đồ lưu niệm.

Mỗi món đồ được gắn một mã sản phẩm là một chuỗi ký tự chỉ gồm:
- chữ cái thường (a-z)

• chữ số (0-9)_

Để tiện quản lý, Phúc định nghĩa giá trị của một mã sản phẩm như sau:

- Xét các đoạn ký tự số liên tiếp trong chuỗi
- Mỗi đoạn đó được coi là một số nguyên (có thể có số 0 ở đầu)
- Giá trị của mã là tổng các số đó
- Nếu chuỗi không chứa chữ số nào thì giá trị bằng 0

Ví dụ:

• ab12cd34 → có các số 12 và 34 → tổng = 46_
• a001b2 → có các số 001 và 2 → tổng = 1 + 2 = 3_
• abc → không có số → tổng = 0_

Sau đó, Khoa yêu cầu sắp xếp danh sách mã sản phẩm theo thứ tự:

1. Giá trị tăng dần

1. Nếu bằng nhau → chuỗi có độ dài nhỏ hơn đứng trước_
   3. Nếu vẫn bằng nhau → so sánh từ điển (lexicographically)

Hãy giúp nhóm bạn sắp xếp lại danh sách mã sản phẩm.

Input

- Dòng đầu tiên chứa số nguyên \(n\) — số lượng mã sản phẩm
- \(n\) dòng tiếp theo, mỗi dòng là một chuỗi \(s\)

Ràng buộc:

- \(1 \le n \le 10^5\)
- Tổng độ dài tất cả các chuỗi không vượt quá \(10^6\)
- Mỗi chuỗi chỉ gồm ký tự a-z và 0-9

Output

• In ra \(n\) dòng — danh sách mã sản phẩm sau khi sắp xếp

Example

5
ab12cd34
a001b2
abc
z9z9
a10

abc
a001b2
a10
z9z9
ab12cd34