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.