题目内容

在整理计算机中的文件目录时，文件夹名称通常会混合使用大小写字母和数字。为了便于人工查阅，需要对这些名称进行一次综合排序：既考虑字符顺序，也考虑连续数字所表示的实际数值大小。

排序前先将每个文件夹名称拆成若干段。拆分方式如下：

• 遇到连续的数字字符时，将这些字符合并为一个数字段，并去掉前导零后得到该段的整数值；
• 遇到字母字符时，每个字母单独作为一个字母段，其比较值为该字母的 ASCII 码。

两个名称按以下规则决定先后：

• 从左到右逐段比较。

• 若当前位置上一方是数字段而另一方是字母段，则数字段所属名称排在前面。

• 若两段均为数字段，则按去掉前导零后的整数值从小到大排列。

• 若两段均为字母段，则按 ASCII 码值从小到大排列；这样区分大小写，A 到 Z 的值小于 a 到 z 的值。

• 如果逐段比较直到某一个名称已经结束仍未分出差异，则较短的名称排在前面。

• 如果两个名称解析出的段序列完全一致，则它们的排序键相同，此时保持输入时的相对顺序。

约束条件：

• 文件夹数量 n 满足 $1 \le n \le 100$。
• 每个文件夹名称的长度在 $1$ 到 $127$ 之间。
• 名称只由大小写字母和数字字符组成。
• 一段连续数字字符的长度不超过 $9$。

输入描述

第一行包含一个整数 n，表示待排序的文件夹名称数量。 接下来 n 行，每行包含一个文件夹名称字符串。按照输入顺序，这些名称依次记为 v[0] 到 v[n-1]。

输出描述

按排序后的顺序，每行输出一个文件夹名称。

样例1

输入

6
file10
file2
FileA
file01
file1
fileA

输出

FileA
file01
file1
file2
file10
fileA

说明

输入包含 6 个名称。每个名称拆成若干段：字母每字符一段，连续数字合并为整数值段。

FileA 的首字母 F 的 ASCII 码为 70，而其他以 f 开头的名称首字母 ASCII 码为 102，所以 FileA 排在最前。其余以 f 开头的名称前四段均依次为 f、i、l、e，从第 5 段开始比较。

file01 和 file1 的第 5 段都是数字段 1，排序键完全一致，因此按输入顺序保持 file01 在 file1 前。file2 的数字段为 2，file10 的数字段为 10，因此 file2 排在 file10 前。fileA 的第 5 段是字母段 A，而数字段总是排在字母段前，因此 fileA 排在所有数字段名称之后。最终输出如上。

样例2

输入

4
abc10
abc2
abc
abc0

输出

abc
abc0
abc2
abc10

说明

输入包含 4 个名称。abc 是其他名称的共同前缀，逐段比较到 abc 结束时仍未分出差异，因此较短的前缀 abc 排在最前。剩余名称的前三段均为 a、b、c，第 4 段分别是数字段 10、2、0。去掉前导零后按整数值比较，有 $0 < 2 < 10$，所以顺序为 abc0、abc2、abc10。

样例3

输入

1
A1b02

输出

A1b02

说明

输入只有 1 个名称 A1b02，没有需要比较的对象，因此直接按原样输出。