Problem Statement

There is an $N \times N$ grid $X$. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. We call two cells that share an edge adjacent.

Cell $(i,j)$ is painted with color $X_{i,j}$. The color is one of $1,2,3,4$, and adjacent cells are painted with different colors.

You will prepare an $N \times N$ grid $Y$ and paint each cell. Let $Y_{i,j}$ denote the color painted on cell $(i,j)$ of $Y$.

Find one way of painting that satisfies the following conditions.

• The color of each cell of $Y$ is one of $1,2,3,4$. Adjacent cells may have the same color.
• For any two adjacent cells $(i_1,j_1)$ and $(i_2,j_2)$, the following holds.

It can be proved that a way of painting satisfying the conditions always exists.

Constraints

• $2 \le N \le 500$
• $1 \le X_{i,j} \le 4$
• Adjacent cells of $X$ are painted with different colors.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
X_{1,1} X_{1,2} \ldots X_{1,N}
X_{2,1} X_{2,2} \ldots X_{2,N}
\vdots
X_{N,1} X_{N,2} \ldots X_{N,N}

Output

Output a $Y$ satisfying the conditions in the following format:

Y_{1,1} Y_{1,2} \ldots Y_{1,N}
Y_{2,1} Y_{2,2} \ldots Y_{2,N}
\vdots
Y_{N,1} Y_{N,2} \ldots Y_{N,N}