Our society is plannig to launch a new registration portal. Each time a new user wants to register, he sends to the system a request with his name.
If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration.
If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1,name2,....), among these numbers the least i is found so that namei does not yet exist in the database.
Input Format:
The first line contains number n .
The following n lines contain a string.
Output Format :
Print n lines:
OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.
Constraints:
1 ≤ n ≤ 105
1≤length of string≤32