Book Identifier Sorting

You are given n book identifiers. Each identifier is composed of two parts: an alphabetical part and a numerical part. The alphabetical part consists of letters only, while the numerical part consists of digits that form a non-negative integer (leading zeros are allowed, e.g. "002" is interpreted as 2).

Formally, for each book identifier \(s\), let \(A(s)\) be the sequence of letters in the order they appear, and let \(N(s)\) be the integer represented by all digits in \(s\).

Your task is to sort the list of book identifiers primarily in lexicographical order by \(A(s)\), and if two identifiers have the same alphabetical part, then sort them by the numerical value \(N(s)\) in ascending order.

inputFormat

The first line contains an integer n indicating the number of book identifiers. The following n lines each contain one book identifier, which is a non-empty string.

outputFormat

Output the sorted list of book identifiers, one per line.

1
Book1

Book1