Задача №111232. Сканворд

Маленький Тёма недавно начал изучать буквы. На днях ему попался сканворд, который разгадывала его любимая бабушка. Артём долго крутил его в руках, но так и не смог понять, для чего он нужен, и что с ним нужно сделать. Тогда в его маленькую голову пришла большая и светлая мысль.

Сканворд — разновидность кроссворда. Полем сканворда является прямоугольная таблица, состоящая из M строк и N столбцов, внутри которой расположены вопросы, на которые нужно дать ответ, изображения и клетки для записи ответа.

Для каждого столбца Тёма захотел выбрать одну букву, которая встречается в нём чаще всего. Если таких букв несколько, то Артём выбирает любую из них. Затем все выбранные буквы Артём записывает в одну строку и получает слово. Обратите внимание, что Тёма слишком мал, чтобы различать регистр букв, т.е. он считает строчные и прописные буквы одинаковыми.

Артём хочет, чтобы записанное слово было как можно красивее. Слово S1 считается красивее слова S2, если S1 лексикографически меньше S2.

Помогите Артёму найти самое красивое слово из всех, которые он может получить.

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

Первая строка содержит целые числа N и M, разделённые пробелом. В следующих M строках записано по N символов, описывающих клетки сканворда. Если в клетке стоит пробел, значит бабушка не смогла отгадать слово, к которому относится данная клетка. Символ '#' означает, что эта клетка является частью изображения. Символ '?' означает, что в этой клетке находится вопрос. В противном случае в клетке записан один из символов ['A'..'Z', 'a'..'z'], означающих, что бабушка отгадала слово, к которому относится эта клетка. Регистр буквы значения не имеет.

Гарантируется, что в каждом столбце есть хотя бы одна буква.

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

Выведите самое красивое слово из тех, которые может получить Артём.

Примеры тестов

Входные данные
4 4
Aguc
?ful
ag#l
word
Выходные данные
agul

Примечание

Тесты в этой задаче состоят из пяти групп:

  1. 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
  2. 1. Тесты 2 - 12. Тесты с ограничением 1 ≤ N, M ≤ 50, в сканворде встречаются только прописные буквы. Группа тестов оценивается в 10 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. 2. Тесты 13 - 25. Тесты с ограничением 1 ≤ N, M ≤ 50, в сканворде встречаются только буквы. Группа тестов оценивается в 10 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. 3. Тесты 26 - 34. Тесты с ограничением 1 ≤ N, M ≤ 50. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.
  5. 4. Тесты 35 - 50. Тесты с ограничением 1 ≤ N, M ≤ 1000. Группа тестов оценивается в 60 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3 и 4 группы.

Сдать: для сдачи задач необходимо войти в систему