[AGC066A] Adjacent Difference

#### 题目大意 给定一个大小为 $n*n$ 的数组 $A$ 和数字 $d$ ， 和数组中的每个数字 $A_{i,j}$ ， 你可以对每个数字进行加上一个数或减去一个数的操作 ， 使得每个数字与其相邻数字的差的绝对值大于等于 $d$ 。 并且对于每个操作值的绝对值之和不超过 $\frac{1}{2}dn^2$ 。 #### 输入格式 第一行输入两个数字 $n,d$ 。 接下来 $n$ 行 ，每行输入$n$ 个数字 ， 即输入数组 $A$ 。 #### 输出格式 输出 $n$ 行 ，每行 $n$ 个数 ，表示更改后符合条件的数组。

[problemUrl]: https://atcoder.jp/contests/agc066/tasks/agc066_a $ N $ 行 $ N $ 列のマス目があります．上から $ i $ 行目，左から $ j $ 列目のマスをマス $ (i,j) $ と表します． 各マスには整数がひとつずつ書き込まれており，はじめマス $ (i,j) $ に書き込まれている整数は $ A_{i,j} $ です． あなたは次の操作を繰り返し行うことができます： - $ 1\leq\ i,\ j\leq\ N $ を満たす整数 $ i,j $ および整数 $ x $ を選び，$ A_{i,j} $ に $ x $ を加える．この操作にはコストが $ |x| $ かかる． 正整数 $ d $ が与えられます．あなたの目標は次の条件が成り立つようにすることです： - 上下左右の $ 4 $ 方向に隣接する $ 2 $ マスに書き込まれている整数の差は $ d $ 以上である．より形式的には，次の $ 2 $ 条件が成り立つ： - $ 1\leq\ i\leq\ N-1 $, $ 1\leq\ j\leq\ N $ を満たす整数 $ i,\ j $ に対して $ |A_{i,j}-A_{i+1,j}|\geq\ d $． - $ 1\leq\ i\leq\ N $, $ 1\leq\ j\leq\ N-1 $ を満たす整数 $ i,\ j $ に対して $ |A_{i,j}-A_{i,j+1}|\geq\ d $． この目標を，総コスト $ \frac12\ dN^2 $ 以下で達成してください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ d $ $ A_{1,1} $ $ \cdots $ $ A_{1,N} $ $ \vdots $ $ A_{N,1} $ $ \cdots $ $ A_{N,N} $

一連の操作後のマス目の状態を次の形式で出力してください． > $ A_{1,1} $ $ \cdots $ $ A_{1,N} $ $ \vdots $ $ A_{N,1} $ $ \cdots $ $ A_{N,N} $ 条件を満たすマス目の状態が複数存在する場合には，そのどれを出力しても正解となります．総コストを最小化する必要はありません．

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

-2 8 3
3 -9 -4
-2 8 3

5 2
1 5 5 0 3
2 0 2 5 1
5 2 0 5 5
3 7 2 0 1
6 0 4 3 6

0 4 6 1 3
3 1 3 6 1
5 3 0 3 5
2 6 3 1 3
4 0 5 3 6

### 制約 - $ 2\leq\ N\leq\ 500 $ - $ 1\leq\ d\leq\ 1000 $ - $ -1000\leq\ A_{i,j}\leq\ 1000 $ ### Sample Explanation 1 次のように $ 4 $ 回の操作を行うと，マス目の状態が出力例の通りになります． - $ (i,j,x)=(1,2,7) $ として操作を行う． - $ (i,j,x)=(2,2,-5) $ として操作を行う． - $ (i,j,x)=(3,1,-2) $ として操作を行う． - $ (i,j,x)=(3,2,7) $ として操作を行う． コストの総和は $ 7+5+2+7=21 $ であり，これは $ \frac{1}{2}dN^2=\frac{45}{2} $ 以下です．