Given an integer $D$ and an $n \times m$ real-valued matrix $A$, where the element at row $i$ and column $j$ is $a_{i,j}$ and $0 \le a_{i,j} \le D$ ($1 \le i \le n, 1 \le j \le m$). You are asked to provide an $n \times m$ binary matrix $B$, where the element at row $i$ and column $j$ is $b_{i,j} \in \{0, 1\}$ ($1 \le i \le n, 1 \le j \le m$).

For a given matrix $A$ and your matrix $B$, we can calculate:

$$p_1 = \max \left\{ \max_{1 \le i \le n} \left| \sum_{j=1}^m \left( b_{i,j} - \frac{a_{i,j}}{D} \right) \right|, \max_{1 \le j \le m} \left| \sum_{i=1}^n \left( b_{i,j} - \frac{a_{i,j}}{D} \right) \right| \right\}$$

$$p_2 = \max_{1 \le i < n, 1 \le j < m} \left| (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} \right|$$

In different test cases, we want the provided matrix $B$ to make either $p_1$ or $p_2$ as small as possible.

Input

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, m$, separated by spaces. $D$ is as defined above, and $n$ and $m$ represent the number of rows and columns of matrix $A$, respectively.

The following $n$ lines each contain $m$ real numbers, describing matrix $A$. The element at row $i$ and column $j$ is $a_{i,j}$, with numbers separated by spaces.

Output

The output should contain an $n \times m$ binary matrix $B$, representing your answer that minimizes $p_c$. The element at row $i$ and column $j$ is $b_{i,j}$. Adjacent integers should be separated by a space.

Examples

Input 1

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

Output 1

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

Input 2

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

Output 2

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

Note

In Example 1, $p_1 \approx 0.4286$, and in Example 2, $p_2 \approx 0.7143$.

Scoring

If your program outputs an invalid result (not a valid $n \times m$ binary matrix), your score for that test case will be 0. Otherwise, we will calculate the $p_c$ corresponding to your output. Let $Total$ be the total points for the test case, and your score for this case will be $YourScore$.

If $c = 1$, then $YourScore = \text{Round}[\max\{1.5 - \max\{p_1, 1\}, 0\} \times 2 \times Total]$

If $c = 2$, then $YourScore = \text{Round}[\max\{2 - \max\{p_2, 1.5\}, 0\} \times 2 \times Total]$

Where $\text{Round}[x]$ denotes the integer nearest to $x$ (rounding half up).

Constraints

$100\%$ of the data: $2 \le n, m \le 700$, $1 \le D \le 1\,000\,000\,000$; $40\%$ of the data: $c = 1$; $60\%$ of the data: $c = 2$.