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:
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.
2 3 8 8 2 6 5 7
110 100
1 2 420 69
10
In the first example, let's consider the laser Pak Chanek shoots into face $$$1$$$ of portal $$$(2, 2)$$$. The laser travels as follows:
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.
Name |
---|