eolymp
bolt
Try our new interface for solving problems
Problems

Video conference

Video conference

Time limit 1 second
Memory limit 256 MiB

Bob is making a video conference software. Whenever a new person joins the conference, Bob displays the person's name in the interface.

However, displaying full name is tedious and takes much space. So he decided to display the shortest prefix which doesn't match with any prefix of any person who has joined earlier.

Let's suppose the first person to enter the conference is alvin. In the call: a.

Now suppose next person to join is alice. The shortest prefix of alice that doesn't match with any prefix of alvin is ali. In the call: a, ali.

If the full name of a new person matches completely with the full name of any person who has joined earlier, he will display the full name and add a suffix which indicates how many times the same name has occurred in the list so far. For example, if another person name alvin joins, the list will look like this: a, ali, alvin 2.

You are given the list of the persons who have joined the call in the chronological order. Your task is to figure out how the final list looks like.

Input data

The first line contains an integer n (1n10^5). The subsequent n line contains a string s[i] (1 ≤ |s[i]| ≤ 10, s[i] contains only lower-case Latin letters) denoting the name of the i-th person to join the call.

Output data

Print the list of people in the video conference. i-th line should contain the prefix of name of the person which doesn't match with any other person who has joined earlier.

Examples

Input example #1
3
alvin
alice
alvin
Output example #1
a
ali
alvin 2
Input example #2
6
mary
stacy
sam
samuel
sam
miguel
Output example #2
m
s
sa
samu
sam 2
mi