Serial Numbers

Interview

Time limit2sMemory limit128 MB

Summary

Sort serial numbers by length, then digit-sum, then a custom lexicographic rule where digits precede letters.

Level: Easy3 of 10
Topics: Sorting, String, Implementation
Solved: No attempts yet

Problem

Dasom owns many guitars, and each guitar has a different serial number. To find the right guitar quickly, she wants to sort the guitars by serial number.

Every serial number consists only of uppercase English letters (A-Z) and digits (0-9).

Serial number A comes before serial number B by the following rules:

If A and B have different lengths, the shorter serial number comes first.
If they have the same length, compare the sum of the digit characters in each serial number. The serial number with the smaller sum comes first. Only digits are included in this sum.
If the first two rules still do not decide the order, compare them lexicographically. In this comparison, digits come before letters.

Given the serial numbers, write a program that prints them in sorted order.

Input

The first line contains the number of guitars, N. N is at most 50.

Each of the next N lines contains one serial number. The length of each serial number is at most 50, and each serial number consists only of uppercase English letters or digits. No two serial numbers are the same.

Output

Print the sorted serial numbers, one per line, over N lines.

Examples4

Example 1

Input

5
ABCD
145C
A
A910
Z321

Expected output

A
ABCD
Z321
145C
A910

Example 2
Input
```
2
Z19
Z20
```
Expected output
```
Z20
Z19
```

Example 3

Input

4
34H2BJS6N
PIM12MD7RCOLWW09
PYF1J14TF
FIPJOTEA5

Expected output

FIPJOTEA5
PYF1J14TF
34H2BJS6N
PIM12MD7RCOLWW09

Example 4

Input

5
ABCDE
BCDEF
ABCDA
BAAAA
ACAAA

Expected output

ABCDA
ABCDE
ACAAA
BAAAA
BCDEF