Дорешка (личный тур)

Соревнование завершилось 03.06.17 в 09:20

A. Автоматизированное тестирование

Ограничение по времени: 6 с.
Ограничение по памяти: 156 МБ

Одна известная компания занимается разработкой алгоритмов поиска текстовой информации. При разработке алгоритмов поиска соответствий в словаре по маске возникла необходимость в реализации автоматизированного тестирования.

Алгоритм поиска соответствий в словаре подразумевает поиск в нём слова, совпадающего с текстом запроса. Алгоритм также подразумевает возможность замены некоторых символов текста поискового запроса на символ ‘?’. В таком случае в искомых словах на позициях, содержащих символ ‘?’, допускается любой символ.

Известно, что используемый словарь состоит из n слов одинаковой длины l. Подготовка автоматизированного тестирования требует, чтобы для каждого возможного значения k (1 \leqslant k \leqslant n) был определен шаблон, которому соответствует ровно k слов из имеющего словаря или же было установлено, что не существует ни одного такого шаблона.

Ваша задача — написать программу, которая по имеющему словарю, состоящему из n слов одинаковой длины l, для всех возможных значений k от 1 до n выведет требуемый текст запроса или определит, что такого текста запроса не существует.

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

Первая строка входных данных содержит два целых числа n и l — количество слов в словаре и длину каждого из них (1 \leqslant n \leqslant 10^{5}, 1 \leqslant l \leqslant 10).

Далее следует n строк, каждая из которых содержит очередное слово используемого словаря. Гарантируется, что все слова различны и состоят ровно из l заглавных букв латинского алфавита.

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

В выходных данных должно содержаться ровно n строк. В k-й строке необходимо вывести текст запроса, которому соответствует ровно k слов из заданного словаря. Если для определенного значения k требуемого текста запроса не существует, k-я строка должна состоять из l символов ‘*’.

Если для некоторого значения k существует несколько подходящих текстов запроса, то разрешается вывести любой из них.

Примеры
Стандартный вводСтандартный вывод
5 4
TAKE
CAKE
LAKE
COKE
SOME
TAKE
?O??
?A??
??KE
????
3 5
TOMSK
AWARD
PRIZE
TOMSK
*****
?????