CF1740G.Dangerous Laser Power

Pak Chanek has an $n \times m$ grid of portals. The portal on the $i$-th row and $j$-th column is denoted as portal $(i,j)$. The portals $(1,1)$ and $(n,m)$ are on the north-west and south-east corner of the grid respectively.

The portal $(i,j)$ has two settings:

• Type $t_{i,j}$, which is either $0$ or $1$.
• Strength $s_{i,j}$, which is an integer between $1$ and $10^9$ inclusive.

Each portal has $4$ faces labelled with integers $0,1,2,3$, which correspond to the north, east, south, and west direction respectively.

When a laser enters face $k$ of portal $(i, j)$ with speed $x_\text{in}$, it leaves the portal going out of face $(k+2+t_{i,j}) \bmod 4$ with speed $x_\text{out} = \max(x_\text{in},s_{i,j})$. The portal also has to consume $x_\text{out} - x_\text{in}$ units of energy.

Pak Chanek is very bored today. He will shoot $4nm$ lasers with an initial speed of $1$, one into each face of each portal. Each laser will travel throughout this grid of portals until it moves outside the grid or it has passed through $10^{100}$ portals.

At the end, Pak Chanek thinks that a portal is good if and only if the total energy consumed by that portal modulo $2$ is equal to its type. Given the strength settings of all portals, find a way to assign the type settings of each portal such that the number of good portals is maximised.

帕克·查内克拥有一个 $n \times m$ 的传送门网格。第 $i$ 行第 $j$ 列的传送门记为传送门 $(i,j)$。传送门 $(1,1)$ 和 $(n,m)$ 分别位于网格的西北角和东南角。

传送门 $(i,j)$ 具有两种属性：

• 类型 $t_{i,j}$，取值为 $0$ 或 $1$；
• 强度 $s_{i,j}$，为介于 $1$ 到 $10^9$（含）之间的整数。

每个传送门有 $4$ 个面，分别标号为整数 $0,1,2,3$，依次对应北、东、南、西方向。

当一束激光以入射速度 $x_\text{in}$ 从传送门 $(i, j)$ 的第 $k$ 个面进入时，它将从编号为 $(k+2+t_{i,j}) \bmod 4$ 的面射出，且出射速度为 $x_\text{out} = \max(x_\text{in},s_{i,j})$。该传送门还需消耗 $x_\text{out} - x_\text{in}$ 单位的能量。

帕克·查内克今天非常无聊。他将向每个传送门的每个面各发射一束激光，共 $4nm$ 束，所有激光初始速度均为 $1$。每束激光将在该传送门网格中持续传播，直至移出网格边界，或已穿过 $10^{100}$ 个传送门为止。

最终，帕克·查内克认为：一个传送门是“好”的，当且仅当该传送门所消耗的总能量对 $2$ 取模的结果等于其类型 $t_{i,j}$。给定所有传送门的强度设置 $s_{i,j}$，请为每个传送门分配类型 $t_{i,j}$，使得“好”传送门的数量最大化。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$) — the number of rows and columns in the grid.

The $i$-th of the next $n$ lines contains $m$ integers, with the $j$-th integer being $s_{i,j}$ ($1 \leq s_{i,j} \leq 10^9$) — the strength of portal $(i, j)$.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$）—— 分别表示网格的行数和列数。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数，其中第 $j$ 个整数为 $s_{i,j}$（$1 \leq s_{i,j} \leq 10^9$）—— 表示传送门 $(i, j)$ 的强度。

Print $n$ lines with each line containing a string of length $m$ consisting of characters $0$ or $1$ representing the type settings. The $j$-th character in the $i$-th string is the type setting of portal $(i, j)$.

If there are multiple solutions, you can output any of them.

输出 $n$ 行，每行包含一个长度为 $m$ 的字符串，该字符串仅由字符 $0$ 或 $1$ 组成，表示排版设置。第 $i$ 行的第 $j$ 个字符表示传送门 $(i, j)$ 的排版设置。

若存在多个解，输出任意一个即可。

In the first example, let's consider the laser Pak Chanek shoots into face $1$ of portal $(2, 2)$. The laser travels as follows:

1. The laser enters face $1$ of portal $(2, 2)$ with speed $1$. It leaves the portal going out of face $3$ with speed $5$. Portal $(2, 2)$ consumes $4$ units of energy.
2. The laser enters face $1$ of portal $(2, 1)$ with speed $5$. It leaves the portal going out of face $0$ with speed $6$. Portal $(2, 1)$ consumes $1$ units of energy.
3. The laser enters face $2$ of portal $(1, 1)$ with speed $6$. It leaves the portal going out of face $1$ with speed $8$. Portal $(1, 1)$ consumes $2$ units of energy.
4. The laser enters face $3$ of portal $(1, 2)$ with speed $8$. It leaves the portal going out of face $2$ with speed $8$. Portal $(1, 2)$ consumes $0$ units of energy.
5. The laser enters face $0$ of portal $(2, 2)$ with speed $8$. It leaves the portal going out of face $2$ with speed $8$. Portal $(2, 2)$ consumes $0$ units of energy.

The illustration of the travel of the laser above is as follows.

As an example, consider portal $(2, 3)$. We can calculate that the total energy consumed by that portal in the end will be $32$. Since $32 \bmod 2 = 0$ and $t_{2,3} = 0$, then it is a good portal.

在第一个例子中，我们考虑 Pak Chanek 射向传送门 $(2, 2)$ 的第 $1$ 个面的激光。该激光的传播路径如下：

1. 激光以速度 $1$ 进入传送门 $(2, 2)$ 的第 $1$ 个面；随后以速度 $5$ 从第 $3$ 个面射出。传送门 $(2, 2)$ 消耗 $4$ 单位能量。
2. 激光以速度 $5$ 进入传送门 $(2, 1)$ 的第 $1$ 个面；随后以速度 $6$ 从第 $0$ 个面射出。传送门 $(2, 1)$ 消耗 $1$ 单位能量。
3. 激光以速度 $6$ 进入传送门 $(1, 1)$ 的第 $2$ 个面；随后以速度 $8$ 从第 $1$ 个面射出。传送门 $(1, 1)$ 消耗 $2$ 单位能量。
4. 激光以速度 $8$ 进入传送门 $(1, 2)$ 的第 $3$ 个面；随后以速度 $8$ 从第 $2$ 个面射出。传送门 $(1, 2)$ 消耗 $0$ 单位能量。
5. 激光以速度 $8$ 进入传送门 $(2, 2)$ 的第 $0$ 个面；随后以速度 $8$ 从第 $2$ 个面射出。传送门 $(2, 2)$ 消耗 $0$ 单位能量。

上述激光传播过程的示意图如下所示。

举例来说，考虑传送门 $(2, 3)$。我们可计算得出，该传送门最终消耗的总能量为 $32$。由于 $32 \bmod 2 = 0$ 且 $t_{2,3} = 0$，因此它是一个“好传送门”。