No difference multiple of four P84298

Consider an $n \times m$ matrix of natural numbers. Here, we say that two numbers $x$ and $y$ of the matrix are neighbours if they are horizontally, vertically or diagonally adjacent. You have to add a number chosen among $\{2, 3, 5, 8\}$ to each number of the matrix. As a result, for every pair of neighbours $x$ and $y$ of the new matrix, $x - y$ cannot be a multiple of four.

Input

Input consists of several cases, each one with $n$ and $m$, both between 1 and 100, followed by $n$ lines, each one with $m$ integer numbers between 0 and $10^9$.

Output

For every given matrix, print your resulting matrix. If there is more than one solution, print any of them. Print a line with 20 dashes after every matrix.