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.