ZS the Coder and Chris the Baboon arrived at the entrance of Udayland. There is a _n_ × _n_ magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a **positive integer** into the empty cell.
Chris tried filling in random numbers but it didn't work. ZS the Coder realizes that they need to fill in a positive integer such that the numbers in the grid form _a magic square_. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid (), each column of the grid (), and the two long diagonals of the grid (the main diagonal — and the secondary diagonal — ) are equal.
Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?
## Input
The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 500) — the number of rows and columns of the magic grid.
_n_ lines follow, each of them contains _n_ integers. The _j_\-th number in the _i_\-th of them denotes _a__i_, _j_ (1 ≤ _a__i_, _j_ ≤ 109 or _a__i_, _j_ = 0), the number in the _i_\-th row and _j_\-th column of the magic grid. If the corresponding cell is empty, _a__i_, _j_ will be equal to 0. Otherwise, _a__i_, _j_ is **positive**.
It is guaranteed that there is exactly one pair of integers _i_, _j_ (1 ≤ _i_, _j_ ≤ _n_) such that _a__i_, _j_ = 0.
## Output
Output a single integer, the positive integer _x_ (1 ≤ _x_ ≤ 1018) that should be filled in the empty cell so that the whole grid becomes a magic square. If such positive integer _x_ does not exist, output - 1 instead.
If there are multiple solutions, you may print any of them.
[samples]
## Note
In the first sample case, we can fill in 9 into the empty cell to make the resulting grid a magic square. Indeed,
The sum of numbers in each row is:
4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.
The sum of numbers in each column is:
4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.
The sum of numbers in the two diagonals is:
4 + 5 + 6 = 2 + 5 + 8 = 15.
In the third sample case, it is impossible to fill a number in the empty square such that the resulting grid is a magic square.
Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 500 $, and let $ A = (a_{i,j}) \in \mathbb{Z}^{n \times n} $ be a matrix such that:
- $ a_{i,j} \in \mathbb{Z}^+ \cup \{0\} $ for all $ 1 \leq i,j \leq n $,
- There exists exactly one pair $ (i_0, j_0) $ such that $ a_{i_0,j_0} = 0 $,
- All other entries satisfy $ a_{i,j} \geq 1 $.
Let $ x \in \mathbb{Z}^+ $ be the value to be placed at position $ (i_0, j_0) $, i.e., $ a_{i_0,j_0} := x $.
Define:
- Row sums: $ R_i = \sum_{j=1}^n a_{i,j} $ for $ i = 1, \dots, n $,
- Column sums: $ C_j = \sum_{i=1}^n a_{i,j} $ for $ j = 1, \dots, n $,
- Main diagonal sum: $ D_1 = \sum_{i=1}^n a_{i,i} $,
- Anti-diagonal sum: $ D_2 = \sum_{i=1}^n a_{i,n+1-i} $.
We require that all row sums, column sums, and diagonal sums are equal to a common value $ S \in \mathbb{Z}^+ $, i.e.:
$$
R_1 = R_2 = \cdots = R_n = C_1 = \cdots = C_n = D_1 = D_2 = S.
$$
Let $ x $ be the unknown value at $ (i_0, j_0) $. Then:
- $ R_{i_0} = \left( \sum_{j=1}^n a_{i_0,j} \right) - 0 + x = \text{sum of row } i_0 \text{ without } x + x $,
- Similarly for $ C_{j_0} $, and if $ i_0 = j_0 $, then $ D_1 $ includes $ x $; if $ i_0 + j_0 = n+1 $, then $ D_2 $ includes $ x $.
Let:
- $ r = \sum_{j=1}^n a_{i_0,j} $ (row sum without the zero),
- $ c = \sum_{i=1}^n a_{i,j_0} $ (column sum without the zero),
- $ d_1 = \sum_{i=1}^n a_{i,i} $ (main diagonal sum without zero if $ i_0 = j_0 $, else unchanged),
- $ d_2 = \sum_{i=1}^n a_{i,n+1-i} $ (anti-diagonal sum without zero if $ i_0 + j_0 = n+1 $, else unchanged).
Then:
- $ R_{i_0} = r + x $,
- $ C_{j_0} = c + x $,
- If $ i_0 = j_0 $, then $ D_1 = d_1 + x $, else $ D_1 = d_1 $,
- If $ i_0 + j_0 = n+1 $, then $ D_2 = d_2 + x $, else $ D_2 = d_2 $.
Let $ S $ be the target common sum.
We require:
1. $ r + x = S $,
2. $ c + x = S $,
3. If $ i_0 = j_0 $, then $ d_1 + x = S $, else $ d_1 = S $,
4. If $ i_0 + j_0 = n+1 $, then $ d_2 + x = S $, else $ d_2 = S $.
From (1) and (2): $ r + x = c + x \Rightarrow r = c $.
Thus, necessary condition: $ r = c $.
Let $ S = r + x $. Then:
- For all rows $ i \ne i_0 $, $ R_i = S \Rightarrow R_i = r + x $,
- For all columns $ j \ne j_0 $, $ C_j = S \Rightarrow C_j = r + x $,
- If $ i_0 = j_0 $, then $ d_1 + x = r + x \Rightarrow d_1 = r $,
- If $ i_0 + j_0 = n+1 $, then $ d_2 + x = r + x \Rightarrow d_2 = r $.
Thus, the value $ x $ is uniquely determined by:
$$
x = S - r
$$
where $ S $ must equal the common value of all other full rows and columns.
**Algorithmic constraints:**
- Let $ S $ be the sum of any row $ i \ne i_0 $ that has no zero (if such exists). If all other rows have zeros, then we cannot determine $ S $ unless from column or diagonal.
- Since only one zero exists, **at least $ n-1 $ rows and $ n-1 $ columns are complete** (no zero). So we can compute $ S $ from any complete row or column.
Thus:
- Let $ S $ be the sum of any row $ i \ne i_0 $ (which is fully filled). If no such row exists (i.e., $ n=1 $), then $ S $ must be determined from the diagonal (but $ n=1 $: only cell is zero, so $ x = S $, and $ S $ must be positive — then any $ x \geq 1 $ works? But we must satisfy diagonals too — for $ n=1 $, row, column, both diagonals are the same cell — so $ x $ must be positive, so any $ x \geq 1 $, but we need *a* value — the problem says output *the* value, implying unique. But for $ n=1 $, if only cell is 0, then any positive integer works? But problem says "if impossible output -1". So for $ n=1 $, we can choose any $ x \geq 1 $, but the problem says "output a single integer", and "if multiple solutions, print any". So we can output 1.
But more carefully:
Actually, for $ n=1 $: the grid is [0]. We must fill x > 0. Then row sum = x, column sum = x, main diagonal = x, anti-diagonal = x. All equal. So any x > 0 works. We can output 1.
But we must check consistency with diagonals only if they contain the zero — which they do.
So general procedure:
1. Find the unique position $ (i_0, j_0) $ where $ a_{i_0,j_0} = 0 $.
2. Compute the sum $ S $ from any **complete** row (i.e., row $ i \ne i_0 $). If no such row exists (only possible if $ n = 1 $), then $ S $ must be determined from a complete column or diagonal. But for $ n=1 $, no complete row/column exists — so we set $ S = x $, and we need to satisfy diagonals, which are the same. So we can choose $ x = 1 $, and it works.
3. However, to be safe: **Compute the sum of every complete row (without zero). If there is at least one, let $ S $ be that value. If all rows have the zero (only possible if $ n=1 $), then compute the sum of every complete column. If still none (n=1), then $ S $ is not fixed yet — but then diagonals are also the same cell. So we can set $ x = 1 $, and it satisfies everything.**
4. But we must check that all other complete rows and columns have the same sum. If not, return -1.
5. Compute $ x = S - r $, where $ r $ is the sum of row $ i_0 $ excluding the zero (i.e., $ r = \sum_{j \ne j_0} a_{i_0,j} $).
6. Similarly, check that $ x = S - c $, where $ c $ is sum of column $ j_0 $ excluding zero — must equal $ S - r $, so $ r = c $ must hold.
7. Check diagonals:
- If $ i_0 = j_0 $, then $ d_1 + x = S \Rightarrow d_1 = S - x = r $ — must hold.
- If $ i_0 + j_0 = n+1 $, then $ d_2 + x = S \Rightarrow d_2 = r $ — must hold.
8. If any of the above fail, return -1.
9. If $ x \leq 0 $, return -1 (must be positive integer).
10. Otherwise, output $ x $.
**Formal Statement:**
Given $ n \in \mathbb{N} $, $ A \in \mathbb{Z}^{n \times n} $, with exactly one $ (i_0, j_0) $ such that $ a_{i_0,j_0} = 0 $, and all other $ a_{i,j} \in \mathbb{Z}^+ $.
Define:
- $ r = \sum_{j=1}^n a_{i_0,j} $ (sum of row $ i_0 $, ignoring zero),
- $ c = \sum_{i=1}^n a_{i,j_0} $ (sum of column $ j_0 $, ignoring zero),
- $ D_1 = \sum_{i=1}^n a_{i,i} $,
- $ D_2 = \sum_{i=1}^n a_{i,n+1-i} $.
Let $ \mathcal{R}_{\text{full}} = \{ R_i \mid i \ne i_0 \} $, the set of sums of all complete rows.
Let $ \mathcal{C}_{\text{full}} = \{ C_j \mid j \ne j_0 \} $, the set of sums of all complete columns.
Let $ S $ be the common value of all elements in $ \mathcal{R}_{\text{full}} \cup \mathcal{C}_{\text{full}} $, if non-empty.
If $ \mathcal{R}_{\text{full}} \cup \mathcal{C}_{\text{full}} = \emptyset $ (i.e., $ n = 1 $), set $ S = 1 $ (arbitrary positive value; will be satisfied by any $ x > 0 $, and we choose minimal).
Otherwise, if $ |\mathcal{R}_{\text{full}} \cup \mathcal{C}_{\text{full}}| > 1 $, return $ -1 $.
Set $ x = S - r $.
Check:
- $ x > 0 $,
- $ r = c $,
- If $ i_0 = j_0 $, then $ D_1 = S - x = r $,
- If $ i_0 + j_0 = n+1 $, then $ D_2 = S - x = r $.
If all conditions hold, output $ x $; else output $ -1 $.