新的电子邮件服务“Berlandesk”将于近期在 Berland 开通。站点管理人员希望尽快启动他们的项目,这就是他们请求您提供帮助的原因。建议您实现站点注册系统的原型。该系统应遵循以下原则工作。
每次新用户想要注册时,他都会向系统发送带有其姓名的请求。如果系统数据库中不存在这样的名称,则将其插入到数据库中,并且用户得到响应OK,确认注册成功。如果该名称已存在于系统数据库中,系统会创建一个新的用户名,将其作为提示发送给用户,并将提示插入数据库中。新名称由以下规则组成。 name 后面依次添加从 1 开始的数字(name1、name2、...),在这些数字中找到最少的 i,因此 namei 在数据库中尚不存在。
输入
第一行包含数字 n (1 ≤ n ≤ 105)。以下 n 行包含对系统的请求。每个请求都是一个非空行,并且由不超过32个字符组成,这些字符都是小写拉丁字母。
输出
打印n行,这是系统对请求的响应:如果注册成功,则为OK;如果请求的名称已被使用,则提示新名称。
示例
输入 #1
4 abacaba acaba abacaba acab
输出 #1
OK OK abacaba1 OK
输入 #2
6 first first second second third third
输出 #2
OK first1 OK second1 OK third1