Ребята из Контур.Старта запустили новый стартап по распознаванию документов. Пользователи сканируют свои накладные, загружают их на наши сервера, а мы распознаем эти данные и обновляем данные в учетной системе. Но для экономии перед отправкой изображения его необходимо сжать до минимально возможного.

Изображение представляет собой прямоугольник n x m, разделенный на nm единичных клеток — пикселей. Каждый пиксель может быть либо черного, либо белого цвета.

Опишем процесс сжатия изображения. Можно разбить все изображение на прямоугольники одинаковых размеров (у всех прямоугольников должна совпадать высота и ширина). Если в результате этого разбиения оказалось, что в каждом прямоугольнике все пиксели имеют одинаковые цвета, то мы можем заменить каждый получившийся прямоугольник на один пиксель соответствующего цвета. Для лучшего понимания процесса сжатия изображения изучите тесты из примера.

Помогите найти сжатие изображения, которое содержит в себе минимальное количество пикселей.

Формат входных данных

Первая строка входных данных содержит два целых числа n и m — высота и ширина исходного изображения соответственно (1 ≤ n,m ≤ 3000).

Далее следует n строк, каждая из которых состоит из m символов, описывающих цвета пикселей исходного изображения. Символ . обозначает пиксель белого цвета, а символ X — пиксель черного цвета.

Формат выходных данных

Выведите описание сжатия изображения. Следуйте тому же формату, что и во входных данных.

Пример