题目描述

一座新城区正在建设智能导航系统。地图上有 $N$ 个路口，每个路口都有一个只包含小写字母的内部名称。由于这些名称主要用于后台管理，因此可能会比较长；但在导航界面、电子路牌和调度终端中，系统希望为每个路口分配一个更短的显示代号，以节省空间并方便展示。

为了避免混淆，显示代号需要满足以下要求：

• 代号仍然只能由小写字母组成；
• 代号不能为空串，且长度必须严格小于原名称；
• 若两个路口的原名称相同，则它们的显示代号必须相同；
• 若两个路口的原名称不同，则它们的显示代号必须不同。

形式化地说，你需要为给定的 $N$ 个字符串各输出一个对应的更短字符串，使得相同输入映射到相同结果，不同输入映射到不同结果。

任意满足上述条件的方案都是合法的。数据保证至少存在一种合法方案。

输入格式

从文件 compress.in 中读入。

第一行一个整数 $N$，表示路口名称的数量。

接下来 $N$ 行，每行一个只包含小写字母的字符串 $s_i$，表示一个路口的原名称。

输出格式

输出到文件 compress.out 中。

输出 $N$ 行，第 $i$ 行输出第 $i$ 个输入字符串对应的显示代号。

输入输出样例

输入样例 1

5
beilu
dongmen
xihu
beilu
nanlu

输出样例 1

bei
dongme
xi
bei
nan

样例 1 说明

下面给出一种合法方案：

• 将路口名称 beilu 的显示代号设为 bei；
• 将路口名称 dongmen 的显示代号设为 dongme；
• 将路口名称 xihu 的显示代号设为 xi；
• 将路口名称 nanlu 的显示代号设为 nan。

其中：

• 相同的名称 beilu 被分配到了相同的代号 bei；
• 不同名称的代号互不相同；
• 每个代号都严格短于对应的原名称。

因此该方案合法。

数据范围和约定

对于 $100\%$ 的数据，满足：

• $1 \le N \le 1000$。
• $2 \le |s_i| \le 50$。