В скором времени в Берляндии откроется новая почтовая служба "Берляндеск". Администрация сайта хочет запустить свой проект как можно быстрее, поэтому они попросили Вас о помощи. Вам предлагается реализовать прототип системы регистрации сайта.
Система должна работать по следующему принципу. Каждый раз, когда новый пользователь хочет зарегистрироваться, он посылает системе запрос name со своим именем. Если данное имя не содержится в базе данных системы, то оно заносится туда и пользователю возвращается ответ OK, подтверждающий успешную регистрацию. Если же на сайте уже присутствует пользователь с именем name, то система формирует новое имя и выдает его пользователю в качестве подсказки, при этом подсказка также добавляется в базу данных. Новое имя формируется по следующему правилу. К name последовательно приписываются числа, начиная с единицы (name1, name2, ...), и среди них находят такое наименьшее i, что namei не содержится в базе данных сайта.
Выходные данные
В выходных данных должно содержаться n строк — ответы системы на запросы: ОК в случае успешной регистрации, или подсказку с новым именем, если запрашиваемое уже занято.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
abacaba
acaba
abacaba
acab
|
OK
OK
abacaba1
OK
|
|
2
|
6
first
first
second
second
third
third
|
OK
first1
OK
second1
OK
third1
|