A15401 | 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.

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)$ .

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.