D. Телефонная книга Поликарпа
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В телефонной книге Поликарпа записаны n телефонных номеров. Каждый номер — это целое 9-значное число, которое начинается с отличной от 0 цифры. Все номера — различны.

На телефоне Поликарпа установлена последняя версия операционной системы Berdroid. При частичном наборе номера Berdroid подсказывает все номера из телефонной книги, подстрокой которых является набранная последовательность цифр. Например, если в телефонной книге Поликарпа записаны три номера 123456789, 100000000 и 100123456, то:

  • при наборе последовательности цифр 00 будут подсказаны номера 100000000 и 100123456,
  • при наборе последовательности цифр 123 будут подсказаны номера 123456789 и 100123456,
  • а при наборе последовательности цифр 01 будет подсказан только номер 100123456.

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

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

Первая строка входных данных содержит единственное целое число n (1 ≤ n ≤ 70000) — количество номеров в телефонной книге Поликарпа.

Далее следуют сами номера по одному номеру в строке. Каждый номер — это целое положительное 9-значное число, которое начинается с цифры от 1 до 9. Все номера — различны.

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

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

Примеры
Входные данные
3
123456789
100000000
100123456
Выходные данные
9
000
01
Входные данные
4
123456789
193456789
134567819
934567891
Выходные данные
2
193
81
91