Відео конференція
Боб розробляє програму для відеоконференцій. Кожного разу, коли новий учасник приєднується до конференції, Боб відображає його ім'я в інтерфейсі.
Однак показувати повне ім'я займає багато місця. Тому він вирішив відображати найкоротший префікс, який не збігається з жодним префіксом будь-якого учасника, що приєднався раніше.
Припустимо, що першим до конференції приєднався 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-а стрічка повинна містити префікс імені учасника, який не збігається з жодним іншим учасником, що приєднався раніше.