#P18775. [Kaist2021]Automatic Sprayer 2

[Kaist2021]Automatic Sprayer 2

Automatic Sprayer 2

题目描述

一块农田被划分为 nn 行 nn 列的单位方格,(i,j)(i,j) 表示第 ii 行、第 jj 列的方格。两格之间的距离为曼哈顿距离:

d((x,y),(i,j))=∣x−i∣+∣y−j∣.d((x,y),(i,j))=|x-i|+|y-j|.

每个方格 (x,y)(x,y) 内可以放置一个自动喷洒器。它向每个方格喷洒 Ax,yA_{x,y} 升药液,其中 Ax,yA_{x,y} 为非负整数。它向方格 (i,j)(i,j) 喷洒所消耗的能量为 d((x,y),(i,j))Ax,yd((x,y),(i,j))A_{x,y}。

设所有喷洒器向方格 (i,j)(i,j) 喷洒所消耗的能量总和为 Ei,jE_{i,j},即

$$E_{i,j}=\sum_{x=1}^{n}\sum_{y=1}^{n}A_{x,y}(|x-i|+|y-j|).$$

给定矩阵 EE,请构造任意一个符合条件的非负整数矩阵 AA。保证至少存在一个元素总和不超过 101210^{12} 的合法矩阵。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行 nn 个整数,第 ii 行第 jj 个整数为 Ei,jE_{i,j}。

输出格式

输出 nn 行,每行 nn 个非负整数,第 xx 行第 yy 个整数为 Ax,yA_{x,y}。有多种合法答案时,输出任意一种即可。

数据范围

  • 2≤n≤10002\le n\le1000。
  • 0≤Ei,j≤10160\le E_{i,j}\le10^{16}。
  • 保证存在非负整数矩阵 AA,其元素总和不超过 101210^{12},且满足上述能量关系。

样例 1

输入

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

输出

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

样例 2

输入

6
43 34 25 24 33 42
42 33 24 23 32 41
41 32 23 22 31 40
40 31 22 21 30 39
39 30 21 20 29 38
48 39 30 29 38 47

输出

0 0 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 5 0 0
0 0 0 0 0 0