Username Registry

Process username requests in order. Accept an unused name with OK. For a used name, append the smallest positive integer suffix that creates a name not used earlier, then reserve that generated name too.

Input

The first line contains q (1 ≤ q ≤ 200000). Each of the next q lines contains one lowercase username of length 1 to 20.

Output

For each request print OK or the generated unique username.

Example 1

Input

6
bob
alice
bob
bob
alice
bob1

Output

OK
OK
bob1
bob2
alice1
bob11

Example 2

Input

5
a
a1
a
a
a1

Output

OK
OK
a2
a3
a11