Прогрессивный NoSQL
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

«Гигачат» — прогрессивная IT-компания, разрабатывающая одноимённую прогрессивную социальную сеть. Недавно Ваня устроился работать в эту компанию. Его текущая задача — реализовать базу данных, которая будет отслеживать регистрации новых пользователей. К сожалению, сейчас Ваня готовится к четвертьфиналу ICPC, поэтому ему нужна Ваша помощь.

Изначально база данных пуста. В течение некоторого времени $$$Q$$$ человек делают по одному запросу в эту базу данных. Каждый запрос представляет собой непустую строку, которая может содержать строчные и заглавные буквы английского алфавита, а также цифры. Длина строки не превышает $$$10$$$. Если в системе ещё нет пользователя, именем которого является данная строка, то необходимо зарегистрировать пользователя с данным именем. В противном случае, к имени пользователя дописывается $$$1$$$ и проверяется наличие такого пользователя в системе. Если такого пользователя нет, то необходимо зарегистрировать пользователя с данным именем (с единицей в конце). Если же такой пользователь уже есть, необходимо вместо $$$1$$$ дописать $$$2$$$, затем (в случае наличия такого пользователя) вместо $$$2$$$ дописать $$$3$$$ и так далее. Ответом на каждый запрос является полученное пользователем имя.

Входные данные

В первой строке дано число $$$Q~(1 \le Q \le 10^5)$$$ — количество запросов. Запросы даны в хронологическом порядке.

В каждой из последующих $$$Q$$$ строк дана непустая строка, которая может содержать только строчные и заглавные буквы английского алфавита, а также цифры. Длина строки не превосходит $$$10$$$.

Выходные данные

Выведите $$$Q$$$ строк, где $$$i$$$-я строка — имя, полученное $$$i$$$-м пользователем.

Пример

Входные данные
11
fst
lem
fst
fst
margot
Margot
margot
fst2
lem1
lem1
lem
Выходные данные
fst
lem
fst1
fst2
margot
Margot
margot1
fst21
lem1
lem11
lem2