Balance Stone

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.

1. After $M$ is written in, every row has the same sum.
2. After $M$ is written in, every column has the same sum.
3. After $M$ is written in, the two diagonals have the same sum.
4. The sums from rules 1, 2 and 3 are all the same value.
5. 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.

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.

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