시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (추가 시간 없음) 1024 MB53282654.167%

문제

A farm is divided into $n \times n$ unit squares of $n$ rows and $n$ columns. Let's define $(i, j)$ as the unit square in the $i$-th row and the $j$-th column ($1 \le i \le n$, $1 \le j \le n$).

The distance between two squares $(i_1, j_1)$ and $(i_2, j_2)$ is defined to be $d\left(\left(i_1, j_1\right), \left(i_2, j_2\right)\right) = |i_1 - i_2| + |j_1 - j_2|$, the Manhattan distance between those two squares.

There are automatic sprayers on this farm that spray fertilizer solution or herbicide so that the owner can produce grain efficiently.

Each sprayer lies entirely in a unit square. The sprayer in $(x,y)$ sprays $A_{x,y}$ liters of solution to all unit squares. $A_{x,y}$ can be any nonnegative integer.

The energy required for the sprayer in $(x, y)$ to spray solution to $(i, j)$ is exactly $d((x, y), (i, j)) \times A_{x,y}$. For each square $(i, j)$, we compute $E_{i,j}$, the sum of energies needed for all sprayers to spray the square $(i, j)$.

Given the matrix $E$, write a program that generates any possible matrix $A$ that corresponds to matrix $E$. $E$ will be given such that there exists such a matrix $A$ of nonnegative integers whose sum is at most $10^{12}$.

입력

The first line contains a single positive integer $n$ ($2 \le n \le 1\,000$).

The next $n$ lines each contain $n$ integers. The $j$-th ($1 \le j \le n$) integer in the $i$-th ($1 \le i \le n$) line is $E_{i,j}$ ($0 \le E_{i,j} \le 10^{16})$. 

The input is designed such that a matrix $A$ consisting of only non-negative integers whose sum is at most $10^{12}$ exists which can yield $E$.

출력

Output $n$ lines, each containing $n$ integers. The $y$-th ($1 \le y \le n$) integer in the $x$-th ($1 \le x \le n$) line should be $A_{x,y}$. 

예제 입력 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

예제 출력 1

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

예제 출력 2

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

출처

University > KAIST > 2021 KAIST 11th ICPC Mock Competition A번