编码员ZS和狒狒克里斯抵达乌代兰入口。入口处有一个n×n的魔法网格,里面填满了整数。 Chris 注意到网格中正好有一个单元格是空的,要进入 Udayland,他们需要在空单元格中填充一个正整数。
Chris 尝试填写随机数,但没有成功。 ZS 编码员意识到他们需要填写一个正整数,以便网格中的数字形成一个幻方。这意味着他必须填写一个正整数,以便网格的每一行 ($$\sum_{r,i}a_{r,i}$$)、网格的每一列 ($$\sum_{i,c}a_{i,c}$$) 以及网格的两条长对角线(主对角线 — $$\sum_{i}a_{i,i}$$ 和次对角线 — $$\sum_{i}a_{i,n-i+1}$$) 相等。
Chris 不知道要填写什么数字,你能帮 Chris 找到正确的正整数来填写或者判断不可能吗?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 500) — 魔法网格的行数和列数。
接下来有 n 行,每行包含 n 个整数。其中第i个中的第j个数字表示ai,j(1≤ai,j≤109或ai,j=0),魔格第i行j列的数字。如果对应的单元格为空,则ai,j将等于0。否则,ai,j为正。
保证恰好存在一对整数 i, j (1 ≤ i, j ≤ n) 使得 ai, j = 0。
输出
输出一个整数,即正整数 x (1 ≤ x ≤ 1018),该正整数 x (1 ≤ x ≤ 1018) 应该被填充到空单元格中,使整个网格成为一个幻方。如果这样的正整数x不存在,则输出-1。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
3 4 0 2 3 5 7 8 1 6
输出 #1
9
输入 #2
4 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
输出 #2
1
输入 #3
4 1 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1
输出 #3
-1
注意
在第一个示例案例中,我们可以将 9 填充到空单元格中,使生成的网格成为幻方。确实,
每行的数字总和为:
4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.
每列中的数字总和为:
4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.
两条对角线上的数字之和为:
4 + 5 + 6 = 2 + 5 + 8 = 15.
在第三个示例案例中,不可能在空方格中填充数字以使生成的网格成为幻方。