Sort File Names with Numeric Extensions

You are given a list of file names. Each file name may follow a specific pattern consisting of a base name (a sequence of letters), an optional numeric part and an optional extension (following a dot).

Your task is to sort these file names using the following key:

$$ key = (\text{base},\, number,\, extension) $$

• The base is the sequence of letters at the beginning of the file name.
• The number is the integer formed by the subsequent digits (if any). If there is no number, treat it as 0.
• The extension is the substring after the dot (if any). If there is no dot, treat the extension as an empty string.

Sort the file names in ascending order according to the tuple key: first by the base (lexicographically), then by the numeric part (numerically), and finally by the extension (lexicographically).

Example 1:
Input: document, file1.txt, file2.txt, image2.jpg, image1.jpg
Output: document, file1.txt, file2.txt, image1.jpg, image2.jpg

Example 2:
Input: a10.txt, a2.txt, a100.txt, b1.txt, a.txt
Output: a.txt, a2.txt, a10.txt, a100.txt, b1.txt

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer n (the number of file names).
2. The following n lines each contain a file name (a non-empty string).

outputFormat

Output the sorted list of file names via standard output (stdout), one file name per line, in the correct order.

## sample

5
document
file1.txt
file2.txt
image2.jpg
image1.jpg

document
file1.txt
file2.txt
image1.jpg
image2.jpg