A. Automatic Sprayer 2
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Examples
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
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
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
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