Background

Translated from Nordic Olympiad in Informatics 2022 Power Grid。If you find that the SPJ is broken, please contact the problem porter qvq。

$\texttt{5s,1G}$。Please do not abuse the judging of this problem.

Problem Description

There is a city consisting of an $N$ by $M$ grid, with a total of $N\times M$ cells. The power consumption of cell $(i,j)$ is denoted by $A_{i,j}$。Here, $A_{i,j}$ can be positive, negative, or $0$。

For cell $(i,j)$, define

$$C_{i, j} = \left| \sum _{k=1}^ N A_{k, j} - \sum _{k=1}^ M A_{i, k} \right|$$

That is, the absolute value of the difference between the total power usage of a column and the total power usage of a row。

Given all $C_{i,j}$, can you construct a valid set of $A_{i,j}$?

The testdata guarantees that at least one solution exists。

Input Format

The first line contains two positive integers $N, M$, with meanings as described in the statement。

In the next $N$ lines, the $j$-th number in line $i$ is $C_{i,j}$, with meaning as described in the statement。

It is guaranteed that at least one solution exists。

Output Format

Output $N$ lines each with $M$ numbers, where the $j$-th number in line $i$ is $A_{i,j}$。

If there are multiple solutions, output any one of them。

You need to ensure that $-2^{31}\le A_{i,j}\lt 2^{31}$。

2 3
3 4 1
6 7 2

1 2 6
5 3 4

3 4
0 0 0 0
0 0 0 0
0 0 0 0

0 0 0 0
0 0 0 0
0 0 0 0

Hint

Constraints

• $1\le N, M\le 1\, 000$；
• $0\le C_{i,j}\le 1\, 000$；
• At least one solution is guaranteed。

Subtasks

Subtask ID	Score	Constraints
$1$	$8$	$N, M, C_{i,j}\le 3$
$2$	$5$	$N, M, C_{i,j}\le 6$
$3$	$11$	$N=1$
$4$	$6$	$N, M\ge 2$，all $C_{i,j}$ are the same
$5$	$15$	$N, M\ge 2$，all $C_{i,j}$ are pairwise distinct
$6$	$5$	$C_{i,j}\le 1$
$7$	$15$	$N=M$
$8$	$25$	$N, M, C_{i,j}\le 100$
$9$	$10$	No additional constraints

Translated by ChatGPT 5