题目描述

最近情报人员得到了一些经过加密的文章，每个单词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前缀，但所取的前缀不能是其它单词的前缀。

这个任务现在就交给你来完成。

解释：“字符串 s1 是 s2 的前缀” 是说把字符串 s2 的后面去掉某些，只保留与 s1 相同长度时，s2 就与 s1 完全相同。如："abc" 是 "abcaade" 和 "abc" 的前缀，但不是 "ababc" 的前缀。

输入格式

第一行一个整数N，表示单词个数。

下面有 N 行，每行一个单词。

数据范围

单词数 N ，1<=N<=50；每个单词长度不超过 50 ；并且单词都由小写字母构成。

保证所给单词没有一个单词是另一个单词的前缀。

输出格式

共 N 行，每行一个单词，是对应上面的 N 个单词的化简后的单词。

样例

3
abc
efg
ijh

a
e
i

3
aac
aad
aae

aac
aad
aae