问题描述

一个字符串的前缀是指从该字符串开头开始的子串。例如，字符串 "carbon" 的前缀有："c"、"ca"、"car"、"carb"、"carbo" 和 "carbon"。注意，在本问题中，空字符串不被视为前缀，但每个非空字符串都被视为其自身的前缀。在日常生活中，我们通常用前缀来缩写单词。例如，"carbohydrate" 通常被缩写为 "carb"。

在本问题中，给定一组单词，你需要为每个单词找到能够唯一标识该单词的最短前缀。

在示例输入中，"carbohydrate" 可以被缩写为 "carboh"，但不能被缩写为 "carbo" 或更短的字符串，因为列表中有其他单词以 "carbo" 开头。

精确匹配会覆盖前缀匹配。例如，前缀 "car" 精确匹配单词 "car"。因此，可以明确无误地认为 "car" 是 "car" 的缩写，而不是 "carriage" 或列表中其他以 "car" 开头的单词的缩写。

输入

输入包含至少两行，但不超过 $1000$ 行。每行包含一个由 $1$ 到 $20$ 个小写字母组成的单词。

输出

输出的行数与输入相同。每行输出包含输入中对应行的单词，后跟一个空格，以及能够唯一标识该单词的最短前缀。

示例输入 1

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

示例输出 1

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

来源

洛基山 2004