K. The Devil
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

People use abbreviations to express succinctly. This can lead to trouble when two phrases share the same abbreviation. For example, searching the term "CCPC" online, you will find not only the desired "China Collegiate Programming Contest", but also "China Car Performance Challenge", "Competition and Consumer Protection Commission", etc.

However, nobody will drive a car while writing code. You decide to resolve the problem by assigning a distinct initialism-like abbreviation to every phrase you often use. There are $$$n$$$ phrases, each consisting of some words in lowercase and uppercase English letters. To create an abbreviation for a phrase, a non-empty prefix of each word in the phrase is chosen and then concatenated in order. For example, "ChCoPrCo" and "CCPContest" are valid abbreviations for "China Collegiate Programming Contest", but "CCCP" and "CCPiC" are not. Each phrase is abbreviated independently from the other phrases: the same word can be abbreviated differently in different phrases.

Construct an abbreviation scheme so that the total length of all abbreviations is minimized, while ensuring $$$n$$$ abbreviations are distinct.

Input

The first line of input contains an integer $$$n~(1 \leq n \leq 128)$$$, representing the number of phrases.

The next $$$n$$$ lines each contain a non-empty phrase consisting of no more than $$$128$$$ non-empty words separated by single spaces. Each word consists of no more than $$$128$$$ lowercase and uppercase English letters only. It is guaranteed that no two phrases are identical.

Output

If there is no possible solution, print "no solution" in a single line.

Otherwise, print $$$n$$$ lines where the $$$i$$$-th line contains the abbreviation of the $$$i$$$-th phrase in the solution, in the order given by input. If there are multiple solutions, print any.

Examples
Input
5
automated teller machine
active teller machine
active trouble maker
always telling misinformation
American Teller Machinery
Output
atm
atma
actm
atem
ATM
Input
5
Forest Conservation Committee Forum
Fuming Corruption Collusion Federation
Fulsome Cash Concealment Foundation
Funky Crony Capitalism Facilitator
Funny Cocky Cocky Funny
Output
FCCF
FCoCF
FuCCF
FCCFa
FCCFu
Input
3
A AA
AA A
A A A
Output
no solution