AT_arc225_a.Four Coloring

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.

• If $|X_{i_1,j_1} - X_{i_2,j_2}|=1$, then $|Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2$.

• If $|X_{i_1,j_1} - X_{i_2,j_2}|\ge2$, then $|Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1$.

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

存在一个 $N \times N$ 的网格 $X$。记 $(i,j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。我们将共享一条边的两个格子称为相邻。

格子 $(i,j)$ 被染成颜色 $X_{i,j}$。颜色取自 $\{1,2,3,4\}$，且任意两个相邻格子的颜色互不相同。

你需要构造一个 $N \times N$ 的网格 $Y$ 并对每个格子染色。记 $Y_{i,j}$ 表示 $Y$ 中格子 $(i,j)$ 所染的颜色。

请找出一种满足以下条件的染色方案：

• $Y$ 中每个格子的颜色取自 $\{1,2,3,4\}$。相邻格子的颜色可以相同。

• 对任意一对相邻格子 $(i_1,j_1)$ 和 $(i_2,j_2)$，满足以下条件：

  • 若 $|X_{i_1,j_1} - X_{i_2,j_2}|=1$，则 $|Y_{i_1,j_1} - Y_{i_2,j_2}|\ge 2$；
  • 若 $|X_{i_1,j_1} - X_{i_2,j_2}|\ge2$，则 $|Y_{i_1,j_1} - Y_{i_2,j_2}|\le 1$。

可以证明：满足上述条件的染色方案一定存在。

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}$

输入从标准输入给出，格式如下：

$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 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}$

输出一个满足以下条件的 $Y$，格式如下：

$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}$

Sample 1 Explanation:
For the input $X$ and the output $Y$, for example, looking at the two adjacent cells $(1,1)$ and $(1,2)$, we have the following.

• $|X_{1,1} - X_{1,2}| = |1 - 2| = 1$
• $|Y_{1,1} - Y_{1,2}| = |4 - 1| = 3$

Also, looking at the two adjacent cells $(2,2)$ and $(3,2)$, we have the following.

• $|X_{2,2} - X_{3,2}| = |1 - 3| = 2$
• $|Y_{2,2} - Y_{3,2}| = |3 - 4| = 1$

In this way, it can be confirmed that $Y$ satisfies the conditions for any two adjacent cells, so this is a correct answer.

Sample 2 Explanation:
Adjacent cells of $Y$ may have the same color.

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.

样例 1 解释：
对于输入 $X$ 和输出 $Y$，例如考察相邻的两个格子 $(1,1)$ 和 $(1,2)$，我们有以下关系：

• $|X_{1,1} - X_{1,2}| = |1 - 2| = 1$
• $|Y_{1,1} - Y_{1,2}| = |4 - 1| = 3$

再考察相邻的两个格子 $(2,2)$ 和 $(3,2)$，我们有以下关系：

• $|X_{2,2} - X_{3,2}| = |1 - 3| = 2$
• $|Y_{2,2} - Y_{3,2}| = |3 - 4| = 1$

以此类推，可以验证：对任意一对相邻格子，$Y$ 均满足题目条件，因此这是一个正确答案。

样例 2 解释：
$Y$ 中的相邻格子可以具有相同的颜色。

约束条件

• $2 \le N \le 500$
• $1 \le X_{i,j} \le 4$
• $X$ 中的相邻格子颜色互不相同。
• 所有输入值均为整数。