You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

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

## Examples
```input
2 3
8 8 2
6 5 7
```
```output
110
100
```
-----
```input
1 2
420 69
```
```output
10
```

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

Now solve the problem and return the code.