Видео конференция
Боб делает программное обеспечение для видеоконференций. Каждый раз, когда новый человек присоединяется к конференции, Боб отображает его имя в интерфейсе.
Однако отображение полного имени утомительно и занимает много места. Поэтому он решил отобразить самый короткий префикс, который не совпадает ни с одним префиксом любого человека, присоединенного ранее.
Предположим, что первым вошел в конференцию alvin. Список участников выглядит так: a.
Пусть следующим присоединившимся человеком будет alice. Кратчайшим префиксом alice, не совпадающим ни с каким префиксом alvin, будет ali. Список участников выглядит так: a, ali.
Если полное имя нового человека полностью совпадает с полным именем любого человека, который присоединился ранее, Боб отобразит полное имя и добавит суффикс, который указывает, сколько раз одно и то же имя встречалось в списке до сих пор. Например, если присоединится человек с именем alvin, то список будет выглядеть следующим образом: a, ali, alvin 2.
Вам предоставляется список лиц, присоединившихся к конференции в хронологическом порядке. Ваша задача - выяснить, как выглядит окончательный список.
Входные данные
Первая строка содержит количество участников конференции n (1 ≤ n ≤ 10^5). Каждая из следующих n строк содержит s[i] (1 ≤ |s[i]| ≤ 10, s[i] содержит только прописные латинские буквы) - имя i-го человека при вызове.
Выходные данные
Выведите список людей на видео конференции. i-ая строка должна содержать префикс имени человека, который не совпадает с любым другим человеком, присоединившегося ранее.