There is an $N \times M$ matrix $A$, where each cell $A_{i,j}$ can be a positive integer, a negative integer, or $0$.
For each cell $(i,j)$, we define:
$$C_{i, j} = \left| \sum _{k=1}^ N A_{k, j} - \sum _{k=1}^ M A_{i, k} \right| $$
Given all $C_{i,j}$, can you construct a valid set of $A_{i,j}$?
It is guaranteed that at least one solution exists.
Input
The first line contains two positive integers $N$ and $M$.
The next $N$ lines each contain $M$ integers, where the $j$-th number in the $i$-th line is $C_{i,j}$, as defined in the problem statement.
It is guaranteed that at least one solution exists.
Output
Output $N$ lines, each containing $M$ integers, where the $j$-th number in the $i$-th line is $A_{i,j}$.
If there are multiple solutions, any valid solution is acceptable.
You must ensure that $-2^{31} \le A_{i,j} < 2^{31}$.
Examples
Input 1
2 3 3 4 1 6 7 2
Output 1
1 2 6 5 3 4
Input 2~6
See the provided files. Note: Sample outputs for 2~6 are not provided.
Constraints
- $1 \le N, M \le 1\,000$
- $0 \le C_{i,j} \le 1\,000$
- It is guaranteed that at least one solution exists.
| Subtask ID | Score | Constraints |
|---|---|---|
| $1$ | $8$ | $N, M, C_{i,j} \le 3$ |
| $2$ | $7$ | $N, M, C_{i,j} \le 6$ |
| $3$ | $12$ | $N=1$ |
| $4$ | $10$ | $N, M \ge 2$, all $C_{i,j}$ are identical |
| $5$ | $18$ | $N, M \ge 2$, all $C_{i,j}$ are distinct |
| $6$ | $10$ | $C_{i,j} \le 1$ |
| $7$ | $12$ | $N=M$ |
| $8$ | $15$ | $N, M, C_{i,j} \le 100$ |
| $9$ | $8$ | No additional constraints |