Problem Description

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

For the given matrix $A$ and the provided 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}|\}$$

In different test cases, we hope that the provided matrix $B$ can minimize either $p_1$ or $p_2$.

Input Format

The first line contains an integer $c$, which can be either $c=1$ indicating the minimization target is $p_1$, or $c=2$ indicating the minimization target is $p_2$.

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

The following $n$ lines describe matrix $A$, with each line containing $m$ real numbers. The $i$-th row and $j$-th column of matrix $A$ is represented by $a_{ij}$, with numbers separated by a space.

Output Format

Output a single $n$ by $m$ binary matrix $B$, representing the solution that minimizes $p_c$. The $i$-th row and $j$-th column of matrix $B$ is represented by $b_{ij}$, with integers separated by a space.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

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

Sample Output #2

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

Notes/Hints

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

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

For $100\%$ of the test cases, $2 \le n, m \le 700$ and $1 \le D \le 10^9$.

见题面 Input 部分

见题面 Output 部分