5.1 New Era School
(RankList for this Question)
Score: 30pts
Time Limit: 2.00 sec
A new school named "New Era School" is going to be opened in Dharavi. The principal wants to open the school as soon as possible, that's why she is asking you to help. You have to create an admission system. The system should take care of the following points.

When a new student wants to join the school, he has to fill a form with his name. If another student with the same name doesn’t exist, he/she is admitted to the school, and the student gets the response ‘OK’ to confirm successful admission. If the student with the same name already exists in the school, the system changes the student name to a new name and sends it to the student, and then the student is admitted to the school with the new name. The new name is formed by the following rule.

If a name is repeated then the new name will be ‘nameI’ where I start from 1,2,3…
If the same name (eg: Rahul) occurs 3 times, then the first occurrence will be ‘Rahul, the second occurrence will be ‘Rahul1’ and the third occurrence will be ‘Rahul2’ and so on.

1 ≤ n ≤ 10^5, max length of name is 32 char

Input Format
1)The first line contains the number n (1 ≤ n ≤ 10^5). The following n lines contain the student names wanting to take admission in school.
2)Each name is a non-empty line and consists of not more than 32 characters, which are all lowercase English letters.

Output Format
Print n lines, which are responses given to the students: OK in case of successful admission, or a message with a new name, if a student with the same name exists.

Example 1


In the first test case, 1st and 2nd names are unique so OK is printed. The 3rd name is the same as the 1st name so it is changed to ‘abacaba1’. 4th is again unique so OK is printed.

Log In to solve the Question