Balance Stone

Interview

Time limit1sMemory limit512 MB

Summary

One cell of an N by N grid is 0; find the number M that makes all rows, columns, and both diagonals share one common sum, or print -1.

Level: Medium4 of 10
Topics: Implementation, Math, Matrix
Solved: No attempts yet

Problem

Thanojins, a villain who wants to cut the population of the universe in half, is after the Balance Stone, a gem that controls how many people the universe holds. Captain Hakgyu of the Cvengers stands against him and wants to find the Balance Stone first and destroy it.

The Balance Stone is the prize for completing a number puzzle made of $N \times N$ blocks. One block of the puzzle is empty, and the puzzle is complete once you write a number $M$ in that block that satisfies the rules below.

After $M$ is written in, every row has the same sum.
After $M$ is written in, every column has the same sum.
After $M$ is written in, the two diagonals have the same sum.
The sums from rules 1, 2 and 3 are all the same value.
If no number written in place of $M$ satisfies rules 1, 2 and 3, write -1 in the block to finish the puzzle.

Help Captain Hakgyu complete the puzzle and keep the universe at peace.

Input

The first line contains the puzzle size $N$ . ( $2 \le N \le 500$ )

Each of the next $N$ lines contains the $N$ numbers written in the blocks of one row. Each number is a natural number between $1$ and $10^9$ , and the empty block is given as $0$ . One block is empty. When an $M$ that satisfies the rules exists, that $M$ is always a natural number.

Output

Print the number $M$ that satisfies the puzzle rules. Print -1 if no such number exists.

Examples2

Example 1
Input
```
3
6 1 8
7 5 3
2 0 4
```
Expected output
```
9
```
Example 2
Input
```
2
1 0
2 1
```
Expected output
```
-1
```