Laplacian matrices (2) X59053

A square matrix $M$ of size $n\times{n}$ that contains only zeros and ones, and only zeros in the diagonal, is called a binary matrix.

The Laplacian of a binary matrix $M$ is another $n\times{n}$ square matrix $L$ with the following content:

• All cells $L_{ii}$ (i.e. the diagonal of $L$), are equal to the number of ones in row $i$ of $M$.

• Any other cell in $L$ contains the same value than the corresponding cell in $M$ but with opposite sign (since $M$ contains only 0 and 1, these $L$ cells will contain 0 or -1 accordingly).

For example, the following binary matrix $5\times5$:

 0  1  1  0  0
 1  0  0  1  1
 0  1  0  0  1 
 1  1  1  0  1
 0  0  0  0  0

has as Laplacian the following Matrix:

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

• Write a function count_row(a,i) that receives a binary matrix $a$ and a row number $i$, and returns how many 1 there are in the $i$-th row of $a$.

• Write a program that reads a sequence of binary matrices and prints its Laplacian following the format shown in the examples. The program must use the function count_row.

Input

Input is a sequence of cases. A case is a number $n > 0$, the dimension of the coming binary matrix, followed by $n\times{n}$ integers describing the matrix: all of them either 0 or 1, where all the diagonal entries are zero.

Output

The output must contain the Laplacian transform of each of the matrices in the input in the same order. One empty line should appear after each case.