Задача №115242. Магический квадрат
В далеком волшебном царстве жил знаменитый волшебник Мерлин. Он был известен своими магическими способностями и умением создавать магические предметы. Однажды Мерлин создал магический квадрат размера \(n\) на \(n\), в каждой ячейке которого было записано целое число от \(1\) до \(n^2\), при этом все числа были различны. Магический квадрат обладал удивительными свойствами: все строки и все столбцы этого квадрата имели одинаковую сумму чисел.
Однако, в один день, когда Мерлин отвлекся на мгновение, злой колдун Гаргамель проник в его лабораторию и решил навредить. Он поменял местами два числа в этом магическом квадрате, надеясь испортить его магическую силу.
Теперь Мерлину нужна ваша помощь, чтобы определить, какие числа были поменяны местами.
В первой строке дано одно число \(n\) (\(3 \le n \le 1000\)) — размер квадрата. В следующих \(n\) строках дано по \(n\) чисел \(a_{ij}\) (\(1 \le a_{ij} \le n^2\)). Гарантируется, что все числа различны. Гарантируется, что существует два числа, которые можно поменять, чтобы квадрат стал магическим.
Требуется вывести четыре числа \(r_1\), \(c_1\), \(r_2\) и \(c_2\) —номер строки и номер столбца первого числа и номер строки и номер столбца второго числа, которые надо поменять, чтобы квадрат стал магическим. Строки и столбцы нумеруется сверху вниз и слева направо, соответственно, начиная с единицы.
3 6 9 2 3 5 7 8 1 4
1 1 3 3