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