题目描述

给定 $n$ 个仅由小写英文字母组成的字符串 $S_1, S_2, \dots, S_n$。定义两个字符串之间的比较规则如下：

• 对于每个字符 $c \in \{\text{a}, \text{b}, \dots, \text{z}\}$，记其在字符串中的出现次数为 $\text{cnt}_c(S)$。
• 按照字符从 $a$ 到 $z$ 的顺序，依次比较 $\text{cnt}_c(S_i)$ 与 $\text{cnt}_c(S_j)$：
  • 若当前字符 $c$ 的出现次数相同，则继续比较下一个字符；
  • 若出现次数不同，则出现次数 较多 的字符串被认为 更小。
• 若对于所有字符 $a \sim z$，两个字符串的出现次数均相同，则按照字典序比较两个字符串，字典序较小的字符串更小。

字典序说明：给定两个字符串 $A$ 和 $B$，从左到右逐个比较对应位置的字符，直到出现不同字符为止。设在第一个不同的位置上，$A$ 的字符小于 $B$ 的字符，则 $A$ 的字典序小于 $B$。若一个字符串是另一个字符串的前缀，则长度较短的字符串字典序更小。

输入格式

从文件 word.in 中读入数据。

第一行输入一个整数 $n$，表示字符串的数量。

第二行输入 $n$ 个字符串 $S_1, S_2, \dots, S_n$。

输出格式

输出到文件 word.out 中。

输出一行，包含 $n$ 个字符串，表示按照题目定义的比较规则排序后的字符串。

样例 1 输入

5
aab aac adc baa cab

样例 1 输出

aab baa aac cab adc

样例 2 输入

10
a c ab ba aabb bbaa abc cba aaaaab bbbbb

样例 2 输出

aaaaab aabb bbaa abc cba ab ba a bbbbb c

样例 3

见选手目录下的 word/word3.in 和 word/word3.ans。 该测试用例满足测试点 $6 \sim 7$ 的约束条件。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5, 1 \le |s_i| \le 10$。其中 $|s_i|$ 表示字符串 $s_i$ 的长度。

各测试点的附加限制如下表所示：

特殊性质 A：每个字符串的长度均为 1。

点击下载大样例