题目描述

有一个 $H \times W$ 的网格，每个格子中写有一个整数。对于 $1 \leq i \leq H$，$1 \leq j \leq W$，第 $i$ 行第 $j$ 列的格子中写的整数记作 $A_{i,j}$。

你可以进行如下操作任意次（也可以一次都不做）：

• 选择满足 $1 \leq i \leq H-1$ 且 $1 \leq j \leq W-1$ 的整数 $i, j$。
• 选择一个整数 $x$。
• 将 $A_{i,j}$、$A_{i,j+1}$、$A_{i+1,j}$、$A_{i+1,j+1}$ 都加上 $x$。

请你通过若干次操作，使操作后的 $\sum_{i=1}^H \sum_{j=1}^W |A_{i,j}|$ 尽可能小，并输出操作后 $\sum_{i=1}^H \sum_{j=1}^W |A_{i,j}|$ 的值，以及此时网格的状态。

输入格式

输入按以下格式从标准输入读入。

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

输出格式

请输出 $H+1$ 行。第 $1$ 行输出 $\sum_{i=1}^H \sum_{j=1}^W |A_{i,j}|$ 的值。第 $2$ 行到第 $H+1$ 行，按如下格式输出网格的状态：

$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

如果存在多个满足条件的网格状态，输出任意一个都可以。

样例 1

输入

2 3
1 2 3
4 5 6

输出

9
0 -3 -1
3 0 2

样例 2

输入

2 2
1000000000 -1000000000
-1000000000 1000000000

输出

4000000000
2000000000 0
0 2000000000

样例 3

输入

3 4
0 2 0 -2
-3 -1 2 0
-3 -3 2 2

输出

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

说明/提示

限制

• $2 \leq H, W \leq 500$
• $|A_{i,j}| \leq 10^9$

样例解释 1

例如，按如下方式操作，可以得到输出样例中的网格状态：

• 以 $(i, j, x) = (1, 1, -1)$ 进行操作。
• 以 $(i, j, x) = (1, 2, -4)$ 进行操作。 此时，$\sum\_{i=1}^H \sum\_{j=1}^W |A\_{i,j}| = 0 + 3 + 1 + 3 + 0 + 2 = 9$。

样例解释 2

允许进行使 $|A_{i,j}| > 10^9$ 的操作。

由 ChatGPT 4.1 翻译