题目描述

题目背景

一个名为 "Berlanddesk" 的电子邮件系统即将在 Berland 上线运营。该电子邮件系统的管理员希望整个系统的建设可以尽早完成，因此他们找到了资深程序员您，希望您能够为他们开发一个用户注册系统的原型产品。

该系统的运行遵循以下原则：

新用户注册时，他将向系统发送一则内容为其用户名的请求，如果该用户名尚未存在于系统数据库内，则将该用户名插入数据库，同时用户得到回应信息 OK 表示其已经成功注册。如果用户请求的用户名已经存在于数据库内，那么系统将产生一个新的用户名并将其加入数据库。新用户名由用户请求的用户名与正整数 $i$ 构成，$i$ 为使 "用户名i" 尚未存在于数据库内的最小的 $i$。

输入格式

第一行一个整数 $n (1 \le n \le 10^5)$。接下来 $n$ 行，每行表示用户向系统发出的一则请求。每行内容均非空且均为由至多 $32$ 个小写拉丁字母组成的字符串。

输出格式

$n$ 行，每行表示系统对一则请求做出的回应。如果该用户名尚未存在于系统数据库内，则输出 OK。如果用户请求的用户名已经被注册，则输出依照规则生成的新用户名。

输入输出样例 #1

输入 #1

4
abacaba
acaba
abacaba
acab

输出 #1

OK
OK
abacaba1
OK

输入输出样例 #2

输入 #2

6
first
first
second
second
third
third

输出 #2

OK
first1
OK
second1
OK
third1

数据规模与约定

• $1 \le n \le 10^5$
• 用户名长度不超过 $32$，仅包含小写拉丁字母

对于 $30\%$ 的数据，$1 \le n \le 10^3$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$。

下载样例数据

题目样例

ex_regsys1.in ex_regsys1.out
ex_regsys2.in ex_regsys2.out

大样例（按测试分组）

ex_regsys_large1.in ex_regsys_large1.out (第一组，$n = 1000$)
ex_regsys_large2.in ex_regsys_large2.out (第二组，$n = 50000$)