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.

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.

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.