一个农场被划分为 $n \times n$ 个单位正方形，共有 $n$ 行和 $n$ 列。我们定义 $(i, j)$ 为第 $i$ 行第 $j$ 列的单位正方形（$1 \le i \le n, 1 \le j \le n$）。

两个正方形 $(i_1, j_1)$ 和 $(i_2, j_2)$ 之间的距离定义为 $d((i_1, j_1), (i_2, j_2)) = |i_1 - i_2| + |j_1 - j_2|$，即这两个正方形之间的曼哈顿距离。

农场上有自动喷洒器，用于喷洒肥料溶液或除草剂，以便主人能够高效地生产粮食。

每个喷洒器完全位于一个单位正方形内。位于 $(x, y)$ 的喷洒器向所有单位正方形喷洒 $A_{x,y}$ 升溶液。$A_{x,y}$ 可以是任何非负整数。

位于 $(x, y)$ 的喷洒器向 $(i, j)$ 喷洒溶液所需的能量恰好为 $d((x, y), (i, j)) \times A_{x,y}$。

对于每个正方形 $(i, j)$，我们计算 $E_{i,j}$，即所有喷洒器向正方形 $(i, j)$ 喷洒所需的能量之和。

给定矩阵 $E$，编写一个程序，生成任何可能对应于矩阵 $E$ 的矩阵 $A$。给定的 $E$ 保证存在一个元素均为非负整数且元素之和最多为 $10^{12}$ 的矩阵 $A$。

输入格式

第一行包含一个正整数 $n$（$2 \le n \le 1\,000$）。

接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行（$1 \le i \le n$）的第 $j$ 个（$1 \le j \le n$）整数是 $E_{i,j}$（$0 \le E_{i,j} \le 10^{16}$）。

输入数据保证存在一个仅由非负整数组成且元素之和最多为 $10^{12}$ 的矩阵 $A$ 可以产生 $E$。

输出格式

输出 $n$ 行，每行包含 $n$ 个整数。第 $x$ 行（$1 \le x \le n$）的第 $y$ 个（$1 \le y \le n$）整数应为 $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