一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如“carbon”的字串是: “c”，“ca”，“car”，“carb”，“carbo”和“carbon”。注意到这里我们不认为空串是字串，但是每个非空串是它自身的字串。我们现在希望能用前缀来缩略的表示单词。例如，“carbohydrate” 通常用“carb”来缩略表示。现在给你一组单词，要求你找到唯一标识每个单词的最短前缀。
在下面的例子中，“carbohydrate” 能被缩略成“carboh”，但是不能被缩略成“carbo”(或其余更短的前缀) ，因为已经有一个单词用“carbo”开始。
一个精确匹配会覆盖一个前缀匹配，例如，前缀“car”精确匹配单词“car”。因此，“car” 是“car”的缩略语是没有二义性的，“car”不会被当成“carriage”或者任何在列表中以“car”开始的单词。

输入格式:
输入包括至少2行，至多1000行。每行包括一个以小写字母组成的单词，单词长度至少是1，至多是20。

输出格式:
输出的行数与输入的行数相同。每行输出由相应行输入的单词开始，后面跟着一个空格接下来是相应单词的没有二义性的最短前缀标识符。

输入样例:
在这里给出一组输入。例如：

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

输出样例:
在这里给出相应的输出。例如：

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

# 给定一组英文单词（不重复），输出每个单词的最短前缀，最短前缀是指，这个前缀只在这个单词出现，而且是最短的。
# （1）对所有单词进行排序，排序后，拥有公共前缀的字符串会紧邻相挨。
# （2）取出其中的一个单词，获取左右相邻的两个单词与本身的公共前缀。
# （3）两个公共前缀，最长的那个公共前缀，的长度，加上 1，就是本身单词的，最短唯一前缀。

import os

def tmp(words):
    words.sort()  # 先排序
    n, res = len(words), []
    lift, right = 0, 0
    for i, v in enumerate(words):
        if i+1 < n:
            right = len(os.path.commonprefix([v, words[i+1]]))  # 公共前缀的长度
        l = max(lift, right)
        res.append([v, v[0:l+1]])  # 添加
        lift, right = right, 0
    return res

words = list()
try:
    while True:
        line = input("")
        if not line.strip():  # 检查去除空白字符后的字符串是否为空
            break
        words.append(line)
except EOFError:
    pass 
dict_data = {index: value for index, value in enumerate(words)}
res = tmp(list(dict_data.values()))
yuan = list()
for i in dict_data.keys():
    for v in res:
        if dict_data[i] == v[0]:
            yuan.append(v)
for v in yuan:
    print(" ".join(v))