配点 : $700$ 点

問題文

$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}|$ の値および、そのときのマス目の状態を出力してください。

制約

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

入力

入力は以下の形式で標準入力から与えられます。

$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}$

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

2 3
1 2 3
4 5 6

9
0 -3 -1
3 0 2

例えば次のように操作を行うと、出力例のマス目の状態になります。

• $(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 2
1000000000 -1000000000
-1000000000 1000000000

4000000000
2000000000 0
0 2000000000

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

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