描述

有 N 个由小写拉丁字母构成的单词A1, A2, …, AN，其中任意一个单词都不是另一个单词的前缀。（注意，每个单词都是自己的前缀，所以这其中当然没有完全相同的单词。）现在希望把每个单词Ai都改成它的一个非空前缀A’i，使得在A’1, A’2, …, A’N 中仍没有一个单词是另外一个的前缀。在此前提下，使得每个A’i 的长度最小。现在你的任务就是，对于给定的 N 个单词，求出满足条件的方案。

输入格式

输入文件的第一行包含一个正整数 N，表示单词的数目。
之后 N 行，每行一个字符串，表示单词。

输出格式

按照输入文件的顺序输出改动之后的单词，每个单词一行。

样例输入

5
applepi
apollonius
october
octopus
zwei

样例输出

app
apo
octob
octop
z

数据范围与约定

• 对于100%的数据，N≤1000，每个单词最长不超过1000个字符。
• 测试文件中保证有部分规模较小的数据。