2018 程序设计能力实训第一次机考 (下午)

B. DNA 排序题

单点时限: 2.0 sec

内存限制: 256 MB

有若干个 DNA,每个 DNA 可能出现一次或者多次。

统计每个 DNA 出现的次数,然后再按照 DNA 出现次数的升序来输出这些 DNA。对于出现次数相同的 DNA,按照字典顺序排列输出(升序)。

输入格式

第一行是一个整数 $n$。

接下来 $n$ 行,每行一个 DNA。每个 DNA 是由 A, C, G, T 字符组成的,长度不超过 $20$。

  • 对于 $40\%$ 的数据:$1 \le n \le 20$;
  • 对于 $70\%$ 的数据:$1 \le n \le 2000$;
  • 对于所有的数据:$1 \le n \le 200~000$。

输出格式

输出经去重和排序后的 DNA,每个 DNA 一行。

样例

Input
6
CTGGTGGGGAGATGAG
TTGCCACCAACGACGAT
TTGCCACCAACGACGAT
TATGCAG
TATGCAG
TATGCAG
Output
CTGGTGGGGAGATGAG
TTGCCACCAACGACGAT
TATGCAG