| Codeforces Round 369 (Div. 2) |
|---|
| Закончено |
Кодер ZS и Бабуин Крис пришли ко входу в Удайлэнд. У входа они увидели магическую таблицу размера n × n, заполненную целыми числами. Крис заметил, что ровно одна из ячеек таблицы пуста, и для того, чтобы войти в Удайлэнд, друзьям нужно заполнить эту ячейку целым положительным числом.
Крис пробовал заполнять ячейку различными числами, но это не помогло. Тогда Кодер ZS понял, что им нужно вставить целое положительное число такое, что все числа в ячейках образуют магический квадрат. Это значит, что ему нужно вставить такое число, что сумма чисел в каждой строке таблицы (
), в каждом столбце таблицы (
) и в двух больших диагоналях (главной — 
и побочной — 
) равны между собой.
Крис не знает, каким числом нужно заполнить ячейку. Помогите Крису найти подходящее целое положительное число, или определите, что это невозможно.
Первая строка содержит единственное целое число n (1 ≤ n ≤ 500) — количество строк и столбцов в магической таблице.
Далее следуют n строк, каждая из которых содержит n целых чисел, причём j-ое число в i-ой из них равно 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.
Если существует несколько решений, выведите любое из них.
3
4 0 2
3 5 7
8 1 6
9
4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1
1
4
1 1 1 1
1 1 0 1
1 1 2 1
1 1 1 1
-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.
В третьем примере из условия невозможно заполнить пустую ячейку числом так, чтобы сделать таблицу магическим квадратом.
