The Jeweller's Game

Task

John is playing the new hit mobile game: "The Jeweller's Game".

In this game, there is an $N \times N$ board full of different kinds of gems. Let's denote by $(r, c)$ the cell located at the $r$-th row and $c$-th column of the board. Each cell of the board contains a gem. The type of the gem in cell $(r,c)$ is represented by a positive integer $G_{r,c}$.

We group the cells according to the following rule. Cells $a$ and $b$ are in the same group if and only if there exists a sequence of cells $p_0, \ldots, p_k$ such that:

• $p_0 = a$ and $p_k = b$, and
• cells $p_{i-1}$ and $p_i$ are edge-adjacent and are of the same type for each $i = 1, \ldots, k$.

Note that every cell belongs to exactly one group.

The player can improve their score by swapping edge-adjacent cells of the board. Depending on whether the two swapped cells are in the same row or in the same column, we call a swap either horizontal or vertical, respectively. If the two swapped gems are of the same type, then the score of the swap is $0$.
Otherwise, consider the board after performing the swap: the score is the product of the values of the two swapped cells. The value of a cell is the number of cells in its group (including itself).

Find the score of all horizontal and vertical swaps on the board!

Input data

The input file consists of:

• a line containing integer $N$.
• $N$ lines, the $j$-th of which consisting of the $N$ integers $G_{j,1}, \, \ldots, \, G_{j,N}$.

Output data

The first $N$ lines of the output should contain $N-1$ integers each.
On the $i$-th line the $j$-th number ($1 \le i \le N$, $1 \le j < N$) should be the score of the swap of cells $(i, j)$ and $(i, j+1)$.

The next $N-1$ lines of the output should contain $N$ integers each.
The $j$-th number on $i$-th line ($1 \le i < N$, $1 \le j \le N$) should be the score of the swap of cells $(i,j)$ and $(i+1, j)$.

Constraints and clarifications

• $2 \le N \le 1 \ 000$.
• $1 \le G_{r,c} \le 10^6$ for each $r=1\ldots N$ and $c=1 \ldots N$.

Example 1

stdin

3
1 2 1
1 3 2
2 2 2

stdout

2 15 
1 5 
0 0 
0 5 2 
1 4 0

Explanation

In the first sample case, consider the result of the (horizontal) swap of cells $(1,2)$ and $(1,3)$:

The groups of the two swapped cells are marked with red and blue. So the score of the swap is $3 \cdot 5 = 15$.

Example 2

stdin

4
2 1 9 1
1 2 1 1
2 1 2 7
2 9 2 1

stdout

4 4 4 
24 12 0 
8 16 1 
3 3 1 
8 12 4 0 
6 30 4 2 
0 1 0 4