ZS Coder and Chris baboon reached the entrance of Udayland. There, at the entrance, there is a magic grid full of integers (n × n). Chris realized that exactly one of the cells of the grid is empty, and to enter Udayland have to put a positive integer in the empty cell.

Chris tried to fill in random numbers, but it did not work. ZS Coder realizes they have to put a positive integer such that the numbers in the matrix form a magic square. This means you have to place a positive integer such that the sum of the numbers in each row of the matrix (), each column of the matrix (), and the two diagonals (the main diagonal and the diagonal high) are equal.

Chris does not know what number should be placed. Can you help Chris to find the correct positive integer to place or determine that it is impossible?

Spanish version

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 500) - the number of rows and columns of the matrix magic.

In the n lines following are the n integer row. The number jth in the ith line is denoted a[i, j] (1 ≤ a[i, j] ≤ 10⁹ or a[i, j] = 0), the row number ith and jth column magic matrix. If the corresponding cell is empty, a[i, j] is equal to 0. Otherwise, a[i, j] is positive.

It ensures that there is exactly one pair of integers i, j (1 ≤ i, j ≤ n) such that a[i, j] = 0.

Output

A single integer, positive integer x (1 ≤ x ≤ 1.018) to be placed in the empty cell so that the whole matrix becomes a magical array. If there is no positive integer x, output -1.

If there are multiple solutions, you can print any of them.

Example

Input:
3
4 0 2
3 5 7
8 1 6


Output:
9

Input:
4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1

Output:
1

Input:
4
1 1 1 1
1 1 0 1
1 1 2 1
1 1 1 1

Output:
-1

Explanation

In the first example, we can put 9 in the empty cell:

The sum of each row would be: 4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

The sum of each column would be: 4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

The sum of the two diagonals is: 4 + 5 + 6 = 2 + 5 + 8 = 15.

In the third case, it is not possible to find a number that converts the magic matrix.