Problem Description

Given an integer $D$ and a real matrix $A$ with $n$ rows and $m$ columns, the element in row $i$ and column $j$ is $a_{ij}$, and $0 \le a_{ij} \le D$ ($1 \le i \le n$, $1 \le j \le m$). You are asked to provide an $n \times m$ $01$ matrix $B$, whose element in row $i$ and column $j$ is $b_{ij}$ ($1 \le i \le n$, $1 \le j \le m$), where $b_{ij}$ is either $0$ or $1$.

For the given matrix $A$ and your matrix $B$, we can compute:

$$p_1=\max \begin{cases}\max\limits_{ 1 \le j \le m} \{ |\sum_{i=1}^n (b_{ij}-\frac{a_{ij}}{D})|\}\\\max\limits_{1 \le i \le n} \{ |\sum_{j=1}^m (b_{ij}-\frac{a_{ij}}{D})|\}\end{cases}$$$$p_2=\max_{1 \le i \le n,1 \le j \le m} \{|b_{i,j}+b_{i-1,j}+b_{i,j-1}+b_{i-1,j-1}-\frac{a_{i,j}+a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}}{D}|\}$$

For different test cases, we hope that the matrix $B$ you provide can make $p_1$ or $p_2$ as small as possible.

Input Format

The first line contains an integer $c$, which has two possible values: $c=1$ means our minimization target is $p_1$, and $c=2$ means we want $p_2$ to be as small as possible.

The second line contains three integers $D$, $n$, and $m$, separated by a single space. The meaning of $D$ is as described above, and $n$ and $m$ are the number of rows and columns of matrix $A$, respectively.

Then follow $n$ lines, each containing $m$ real numbers describing matrix $A$. The real number in row $i$ and column $j$ is $a_{ij}$, and adjacent numbers are separated by a single space.

Output Format

Output only an $n \times m$ $01$ matrix $B$, representing the answer you found that makes $p_c$ as small as possible. The number in row $i$ and column $j$ is $b_{ij}$. Adjacent integers are separated by a single space.

1
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5

0 1 0 1
1 0 1 0
0 1 0 1

2
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5

0 1 0 1
1 0 1 0
0 1 0 1

Hint

For $40\%$ of the testdata, $c=1$.

For $60\%$ of the testdata, $c=2$.

For $100\%$ of the testdata, Constraints: $2 \le n ,m \le 700$, $1 \le D \le 10^9$.

Translated by ChatGPT 5