В телефонной книге Поликарпа записаны n телефонных номеров. Каждый номер — это целое 9-значное число, которое начинается с отличной от 0 цифры. Все номера — различны.
На телефоне Поликарпа установлена последняя версия операционной системы Berdroid. При частичном наборе номера Berdroid подсказывает все номера из телефонной книги, подстрокой которых является набранная последовательность цифр. Например, если в телефонной книге Поликарпа записаны три номера 123456789, 100000000 и 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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач