当我们交流时,我们学到了很多新信息。然而,沟通的过程需要太多的时间。如果我们看看我们在日常讲话中使用的词语,就会变得很清楚。
我们可以列出许多由许多字母组成的简单单词:“信息”、“技术”、“大学”、“建筑”、“音乐学院”、“冰箱”、“秒表”、“窗台”、“电力”、“政府”等等。当然,我们可以无限地继续列出这些词。
幸运的是,该问题的解决方案已经找到。为了使我们的演讲清晰简洁,我们应该用与它们相似但短得多的单词来替换最初的单词。这个想法还没有被付诸实践,这就是为什么你被选中来改善这种情况。
让我们考虑以下转换单词的形式模型:我们假设一个人可以在聊天中使用 n 个单词。对于每个单词,我们将引入其较短变体的概念。我们将任意单词 s 的较短变体定义为单词 t,它满足以下条件:
- 它作为子序列出现在 s 中,
- 其长度范围为 1 到 4 个字符。
换句话说,单词 t 至少由 1 个且最多 4 个在单词 s 中以相同顺序出现的字符组成。请注意,这些字符不一定紧跟在 s 中。如果首词长度不超过四个字符,则可以不缩短首词。
给你一个包含 n 个不同单词的列表。你的任务是找到一组它们的缩短变体。列表中所有单词的缩写变体应该不同。
输入
输入文件的第一行包含唯一的整数 n (1 ≤ n ≤ 200)。然后 n 行包含一组由小写拉丁字母组成的不同非空单词。每个单词的长度不超过10个字符。
输出
如果解存在,则在输出文件中精确打印 n 行,其中第 i 行表示初始集合中第 i 个单词的缩短变体。如果有多个变体可以解决问题,请打印其中任何一个。如果无解,则打印-1。
示例
输入 #1
6 privet spasibo codeforces java marmelad normalno
输出 #1
pret sps cdfs java mama norm
输入 #2
5 aaa aa a aaaa aaaaa
输出 #2
-1