Registration system
Tag(s):

## Data Structures, Medium, Trie

Problem
Editorial
Analytics

The system works in the following way. Every user has a preferred login $l_i$. System finds the first free login considering possible logins in the following order: $l_i$, $l_{i}0$, $l_{i}1$, $l_{i}2$, ... , $l_{i}10$, $l_{i}11$, ... (you check $l_i$ first; in case it is occupied already, you pick smallest nonnegative integer x such that concatenation of $l_i$ and decimal notation of x gives you free login) and register a user with this login in the system. After the registration this login becomes occupied.

You gave the preferred logins for the n users in chronological order. For each user you have to find a login which he will use in the system.

$INPUT$

The first line of input contains a single integer n $(1 \leq n \leq 2 \cdot 10^{5})$ - a number of users.

Then follow n lines. The i-th of these lines contains $l_i$ - a preferred login for i-th user. $l_i$ is a nonempty string with lowercase english letters and digits.

Guaranteed that the sum of lengths of $l_i$ is not greater than $10^6$.

$OUTPUT$

Print n lines. The i-th of these lines should contain an occupied login for the i-th user.

SAMPLE INPUT
4
lebron
lebron0
lebron1
lebron

SAMPLE OUTPUT
lebron
lebron0
lebron1
lebron2

Explanation

Logins for the first three users are free. Fourth user want to use login "lebron" but the first login which isn't occupied is "lebron2".

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > Searching