A square pizza slice is broken down into a ~N~ by ~N~ grid. Each cell in this grid is assigned a deliciousness value, ~V~. A basic pizza slice would look like the below:

1 2 1
1 3 1
1 1 3

A chef has discovered that folding this square pizza slice in half across a diagonal results in optimal deliciousness per bite, known as a pizza sandwich. The diagonal is represented on the pizza slice as a series of 0s, replacing some deliciousness values from the pizza:

1 2 0
1 0 1
0 1 3

The pizza sandwich is the triangle that results from the folding, with the folded edge of the sandwich marked by the 0s. Each value in the triangle is the sum of the cells that would overlap when the pizza is folded:

4 3 0
2 0
0

The chef wants to know that given a pizza slice and its deliciousness values, can you show him what the pizza sandwich will look like?

Input Specifications

The first line will contain an integer ~N~ where ~3 \le N \le 10^2~.

The next ~N~ lines will each contains ~N~ integers, ~V (1 \le V \le 10^9)~, representing the square pizza slice.

The diagonal will always run from the top right to the bottom left.

Output Specifications

Output the pizza sandwich, with the 0s, in the same format as shown above.

Sample Input

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

Sample Output

2 3 4 0
6 7 0
6 0
0