Dangerous Laser Power
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 3100
Tags: constructive algorithms, dsu, sortings

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.

Input format:
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)$$$.

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example input:
2 3
8 8 2
6 5 7

Example output:
110
100

Example input:
1 2
420 69

Example output:
10

Editorial:
Claim: There is a construction where all portals are good.
We will proceed with the construction.
The key observation of the problem is that for a portal $$$(i,j)$$$ to consume energy, the laser must not enter a portal with a strength greater than or equal to $$$s_{i,j}$$$ before going through portal $$$(i,j)$$$.
Let's say we already have the type settings of all lasers. Consider all possible lasers that at some point enters a certain face of portal $$$(i,j)$$$. We can find the paths of those lasers before entering portal $$$(i,j)$$$ by backtracking in that direction from portal $$$(i,j)$$$.
Consider the first portal in that backtracking path that has a strength greater than or equal to $$$s_{i,j}$$$. Notice that all lasers that starts from portals that are located after that portal in the backtracking path must go through that portal before entering portal $$$(i,j)$$$. Therefore, those lasers cannot make portal $$$(i,j)$$$ use energy, which means they can be ignored.
Using the observation above, we can see that we must only backtrack until we find a portal with a strength greater than or equal to $$$s_{i,j}$$$. Observe that to get the path up to that point, the type settings we should know are only the type settings of portals with strengths smaller than $$$s_{i,j}$$$.
Therefore, the construction can be generated by calculating the type settings of the portals from the smallest to the largest strengths. In each iteration, we use the type settings of the previous portals to find the backtracking paths of the current portal. If we already know the $$$4$$$ backtracking paths for each of the $$$4$$$ directions of that portal, we can find the total energy that portal will consume in the end, which means we can find the type setting for that portal that makes it a good portal.
The naive implementation of this has a time complexity of $$$O(n^2m^2)$$$. Notice that each backtracking path of the portals are just the merging of smaller paths. We can maintain a disjoint set data structure to handle this while maintaining the essential values needed in the calculation of the total energy consumed for each path.
Time complexity: $$$O(nm)$$$