Боб делает программное обеспечение для видеоконференций. Каждый раз, когда новый человек присоединяется к конференции, Боб отображает его имя в интерфейсе.

Однако отображение полного имени утомительно и занимает много места. Поэтому он решил отобразить самый короткий префикс, который не совпадает ни с одним префиксом любого человека, присоединенного ранее.

Предположим, что первым вошел в конференцию alvin. Список участников выглядит так: a.

Пусть следующим присоединившимся человеком будет alice. Кратчайшим префиксом alice, не совпадающим ни с каким префиксом alvin, будет ali. Список участников выглядит так: a, ali.

Если полное имя нового человека полностью совпадает с полным именем любого человека, который присоединился ранее, Боб отобразит полное имя и добавит суффикс, который указывает, сколько раз одно и то же имя встречалось в списке до сих пор. Например, если присоединится человек с именем alvin, то список будет выглядеть следующим образом: a, ali, alvin 2.

Вам предоставляется список лиц, присоединившихся к конференции в хронологическом порядке. Ваша задача - выяснить, как выглядит окончательный список.

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

Первая строка содержит количество участников конференции n (1 ≤ n ≤ 105). Каждая из следующих n строк содержит si (1 ≤ |si| ≤ 10, si содержит только прописные латинские буквы) - имя i-го человека при вызове.

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

Выведите список людей на видео конференции. i-ая строка должна содержать префикс имени человека, который не совпадает с любым другим человеком, присоединившегося ранее.