Shortest Prefixes

A prefix of a string is a substring that starts at the beginning of the string. The prefixes of carbon are c, ca, car, carb, carbo, and carbon. The empty string is not considered a prefix here, but every non-empty string is a prefix of itself.

In everyday language we often abbreviate words by their prefixes. For example, carbohydrate is commonly abbreviated as carb. In this problem you are given a set of words, and for each word you must find the shortest prefix that uniquely identifies it.

For example, carbohydrate can be abbreviated to carboh, but not to carbo (or anything shorter), because other words in the list also begin with carbo.

An exact match overrides a prefix match. For example, the prefix car matches the word car exactly, so car is understood without ambiguity as the abbreviation of car itself, not of carriage or any other word in the list that begins with car.

The input contains at least two and at most $1000$ lines. Each line contains one word made of $1$ to $20$ lowercase letters. All words are distinct.

Output the same number of lines as the input. On each line print the word from the corresponding input line, followed by a single space, and then the shortest prefix that uniquely identifies that word.