描述

有 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个字符。
  • 测试文件中保证有部分规模较小的数据。