All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Registration system
Tag(s):

Medium

Problem
Editorial
Analytics

Your task is to write a registration system.

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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications