题目描述

$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}$ $\ldots$ $A_{1,W}$ $\vdots$ $A_{H,1}$ $\ldots$ $A_{H,W}$

输出格式

$H\ +\ 1$ 行出力してください。 $1$ 行目には、$\sum_{i=1}^H\ \sum_{j=1}^W\ |A_{i,j}|$ の値を出力してください。 $2$ 行目から $H+1$ 行目には、マス目の状態を以下の形式で出力してください。

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

条件を満たすマス目の状態が複数存在する場合は、どれを出力しても正解となります。

题目大意

有一个 $H \times W$ 的整数矩阵，你可以不断选择一个 $2 \times 2$ 的区域都加上同一个整数，你需要最小化矩阵所有元素的绝对值的和，输出最小值并构造方案。

2 3
1 2 3
4 5 6

9
0 -3 -1
3 0 2

2 2
1000000000 -1000000000
-1000000000 1000000000

4000000000
2000000000 0
0 2000000000

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$

Sample Explanation 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 $ です。

Sample Explanation 2

$|A_{i,j}|\ >\ 10^9$ となるような操作も認められています。