Preparing NOJ

# Automatic Sprayer 2

2000ms 1048576K

## Description:

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

## Input:

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:

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

## Sample Input:

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


## Sample Output:

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


## Sample Input:

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


## Sample Output:

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


Info

Provider CodeForces Gym

Code GYM103371A

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:44:57

Related

Nothing Yet