Crossword for a Droid

R2-D2 is solving a crossword made specially for droids. In this crossword, the cells must be filled with digits, not letters.

The crossword is an $n \times m$ grid. Some cells are blocked, and all others are free. A word is a maximal (by inclusion) vertical or horizontal segment of free cells. In other words, a word is a segment of cells in one column or row that is bounded on both sides by the edge of the grid or by blocked cells.

Initially, every free cell contains a digit. The droid's goal is to change the digits so that every word in the crossword is a palindrome. A palindrome is a string that reads the same from left to right and from right to left. The smaller the total change of digits compared with the original, the better. So find a solution where the sum over all free cells of $|$original digit minus solution digit$|$ is minimal.

Help R2-D2 solve the crossword with the minimum total change of digits. It is easy to see that there is always a way to fill the crossword so that all words are palindromes. For example, fill all free cells with the same digit. So a solution always exists.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1\,000$), the grid size.

The next $n$ lines each contain $m$ characters describing the crossword. A character can be . or a digit. The character . is a blocked cell, and a digit $d$ is a free cell that initially contains the digit $d$.

Print the solution in the same format as the input. If there are several solutions, print any of them.

In the first example, the crossword has 6 words, one for each column and each row. In the optimal solution, the total change of digits is 20.

In the second example, besides the words of length 1, there are the words 2020, 05, and 10. In the optimal solution, the total change of digits is 7.