M - Matrix Parity

Time limit: 1 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

We call a matrix of integers even if the sum of the numbers in each row is even and the sum of the numbers in each column is even.


In the following examples, matrices $A$, $B$ and $C$ are even. Matrix $D$ is not even because the second column and the last row have odd sums.  Matrix $E$ is not even because its two columns have odd sums.




Given a matrix $A$, convert it into an even matrix by performing as few as possible of the following type of operation:

  • Select a cell of the matrix and increment its value by 1. You may select the same cell in different operations.

Print any final even matrix that results of executing the minimum number of operations.

Input

The first line contains two integers $r$ and $c$ $(1 \le r, c \le 50)$. Following $r$ lines define matrix $A$. Each line contains $c$ integers with values between $0$ and $100$. The $j$-th number of the $i$-th line is the cell $A_{i, j}$ of the matrix.

Output

Print any even matrix that results from performing the minimum number of operations on matrix $A$.  Then print $r$ rows, with $c$ numbers in each row, describing the matrix after applying the operations.

Sample test(s)

Input
2 3 1 9 3 2 8 9
Output
2 9 3 2 9 9
Input
2 5 1 2 3 4 5 3 1 4 1 5
Output
1 2 4 4 5 3 2 4 2 5
Input
1 2 2 6
Output
2 6