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.

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.

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.

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