题目描述

给定一个整数 $D$，$n$ 行 $m$ 列的实数矩阵 $A$，其第 $i$ 行第 $j$ 列的元素是 $a_{ij}$，且 $0 \le a_{ij} \le D$（$1 \le i \le n$，$1 \le j \le m$）。希望你能由此提供一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$，第 $i$ 行 第 $j$ 列的元素是 $b_{ij}$（$1 \le i \le n$，$1 \le j \le m$），$b_{ij}$ 非 $0$ 即 $1$。

对于给定的 $A$ 矩阵和你提供的 $B$ 矩阵，可以求出

$$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}|\} $$

在不同的测试例子中，我们希望提供的 $B$ 矩阵能使 $p_1$ 或 $p_2$ 尽量小。

输入格式

第一行有一个整数 $c$，有两种取值：$c=1$ 表示我们的最小化目标是 $p_1$，$c=2$ 则表示希望 $p_2$ 尽量小。

第二行有3个整数 $D$，$n$，$m$，相邻的两个数字间用一个空格隔开，$D$ 的含义如上文所述，$n$ 和 $m$ 分别表示 $A$ 矩阵的行数和列数。

以下有 $n$ 行，每行 $m$ 个实数，描述 $A$ 矩阵。其中第 $i$ 行第 $j$ 列的实数表示 $a_{ij}$，相邻的数字用一个空格隔开。

输出格式

仅包含一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$，表示你求出的使 $p_c$ 尽量小的答案。其中第 $i$ 行第 $j$ 列的数字表示 $b_{ij}$。相邻的整数之间用一个空格隔开。

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

提示

对于 $40\%$ 的数据，$c=1$；

对于 $60\%$ 的数据，$c=2$；

对于 $100\%$ 的数据，$2 \le n ,m \le 700$，$1 \le D \le 10^9$。