В телефонной книге Поликарпа записаны n телефонных номеров. Каждый номер — это целое 9-значное число, которое начинается с отличной от 0 цифры. Все номера — различны.
На телефоне Поликарпа установлена последняя версия операционной системы Berdroid. При частичном наборе номера Berdroid подсказывает все номера из телефонной книги, подстрокой которых является набранная последовательность цифр. Например, если в телефонной книге Поликарпа записаны три номера 123456789, 100000000 и 100123456, то:
- при наборе последовательности цифр 00 будут подсказаны номера 100000000 и 100123456,
- при наборе последовательности цифр 123 будут подсказаны номера 123456789 и 100123456,
- а при наборе последовательности цифр 01 будет подсказан только номер 100123456.
Для каждого номера в телефонной книге Поликарпа найдите наименьшую по длине последовательность цифр, которую надо набрать, чтобы Berdroid подсказал только один этот номер.
Выходные данные
Выведите ровно n строк: i-я строка должна содержать наиболее короткую непустую последовательность цифр, при наборе которой будет подсказан только один i-й номер из телефонной книги. Если таких последовательностей несколько, выведите любую из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
123456789
100000000
100123456
|
9
000
01
|
|
2
|
4
123456789
193456789
134567819
934567891
|
2
193
81
91
|