Кроссворд для дроида

• Ограничение времени: 2 секунды
• Ограничение памяти: 512Mb
• Ввод: стандартный ввод или input.txt
• Вывод: стандартный вывод или output.txt

R2-D2 решает кроссворд, составленный специально для дроидов. В этом кроссворде в клеточки нужно писать не буквы, а цифры.

Кроссворд представляет из себя клетчатое поле $$$n \times m$$$. Некоторые клетки заблокированы, а все остальные — свободные. Словом в кроссворде назовем максимальный по включению вертикальный или горизонтальный отрезок свободных клеток. Иными словами, слово — это отрезок клеток одного столбца или строки, ограниченный с обоих сторон краем поля или заблокированными клетками.

Исходно, каждая свободная клетка кроссворда содержит какую-то цифру. Цель дроида — поменять цифры таким образом, чтобы каждое слово в кроссворде являлось палиндромом. Палиндром — это строка, читающаяся одинаково как слева-направо так и справа-налево. При этом, чем меньше суммарное изменение цифр в кроссворде по сравнению с исходными, тем лучше. Поэтому, требуется найти такое решение кроссворда, при котором сумма по всем свободным клеткам модулей разности исходной цифры и цифры в решении, была минимальна.

Помогите R2-D2 решить кроссворд так, чтобы суммарное изменение цифр было минимально. Несложно заметить, что всегда есть способ заполнить кроссворд так, чтобы все слова были палиндромами. Например, заполнить все свободные клетки одинаковыми цифрами. Поэтому, решение всегда существует.

Формат ввода

В первой строке дано два целых числа $$$n$$$ и $$$m$$$ — размеры поля ($$$1 \leq n$$$, $$$m \leq 1 000$$$).

В следующих $$$n$$$ строках дано по $$$m$$$ символов — описание кроссворда. Символы могут быть равны $$$«.»$$$ или цифрам. Символ $$$«.»$$$ соответствует заблокированной клетке. А символ с цифрой $$$d$$$ соответствует свободной клетке, в которой исходно написана цифра $$$d$$$.

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

Выведите описание искомого решения кроссворда в том же формате, что и во входных данных. Если решений несколько, можете вывести любое.