Progressive NoSQL

Interview

Time limit2sMemory limit1024 MB

Summary

Given Q registration requests, each name is assigned as-is if free, otherwise the smallest suffix number (1, 2, ...) that makes it unused is appended.

Level: Easy3 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

<> is a progressive IT company that develops a social network with the same name. Vanya recently joined the company. His current task is to implement a database that tracks new user registrations. Vanya is preparing for the ICPC quarterfinal, so he needs your help.

The database is initially empty. Over time, $Q$ people each send one request to the database. Each request is a non-empty string of uppercase and lowercase English letters and digits, with length at most 10. If no user with that name exists in the system, register a user with that name. Otherwise, append 1 to the name and check whether a user with that name exists. If not, register a user with the name ending in 1. If it does exist, append 2 instead of 1, then append 3 instead of 2 if that name is also taken, and so on. The answer to each request is the name the user received.

Input

The first line contains the number $Q$ ( $1 \le Q \le 10^5$ ), the number of requests. The requests are given in chronological order.

Each of the next $Q$ lines contains a non-empty string. The string contains only uppercase and lowercase English letters and digits. Its length does not exceed 10.

Output

Print $Q$ lines. The $i$ -th line is the name that the $i$ -th user received.

Examples1

Example 1

Input

11
fst
lem
fst
fst
margot
Margot
margot
fst2
lem1
lem1
lem

Expected output

fst
lem
fst1
fst2
margot
Margot
margot1
fst21
lem1
lem11
lem2