Разработчики часто сталкиваются с понятием шаблона регулярных выражений. Под шаблоном обычно понимают строку-образец, состоящую из символов и метасимволов и задающую правило поиска. Такие шаблоны чаще всего используют для того, чтобы проверить, соответствует ли некоторая строка определенным правилам.
В этой задаче шаблоном будет называться строка, состоящая из маленьких латинских букв и знаков вопроса («?»). Знак вопроса в шаблоне — метасимвол, который обозначает произвольную маленькую букву латинского алфавита. Будем считать, что строка удовлетворяет шаблону, если из шаблона можно получить эту строку, заменив знаки вопроса на соответствующие символы. Например, строка aba удовлетворяет шаблонам: ???, ??a, a?a, aba.
Программисты компании R1 любят озадачить друг друга (и сами себя) головоломками. Одна из них выглядит следующим образом: заданы n строк-шаблонов одинаковой длины, нужно найти шаблон, содержащий как можно меньше знаков вопроса, который пересекается с каждым из заданных. Два шаблона пересекаются, если существует строка, которая удовлетворяет и первому и второму шаблону. Сможете ли вы решить эту задачку?
Выходные данные
В единственной строке выведите ответ на задачу — шаблон с минимальным количеством знаков «?», который пересекается с каждым из заданных. Если существует несколько правильных ответов, разрешается вывести любой из них.
Примечание
Рассмотрим первый тестовый пример. Шаблон xab пересекается с каждым из заданных. Шаблон ??? также пересекается с каждым из заданных, но он содержит больше знаков вопроса, поэтому не является оптимальным ответом. Очевидно, xab является оптимальным ответом, так как он совсем не содержит знаков вопроса. Есть и другие оптимальные ответы на этот тест, например: aab, bab, cab, dab и так далее.