Задача №1735. Модель Изинга

Модель Изинга используется в физике для описания твердого тела. Она использует представление кристаллической решетки, в узлах которой находятся атомы.

Рассмотрим плоскую прямоугольную решетку с \(N\) узлами по вертикали и \(M\) узлами по горизонтали (всего \(NM\) узлов). Каждый узел характеризуется своим спином, который может принимать значения +1 или −1.

Соседними считаются узлы решётки, смежные по горизонтали или вертикали. Назовём энергией решетки количество пар соседних узлов с различными спинами.

Дана решётка с известными спинами в каждом узле. Требуется поменять спины ровно двух различных узлов на противоположные таким образом, чтобы энергия полученной решетки была максимальна. Если существует несколько решений, вывести любое из них.

Энергия решетки, приведенной в примере, равна 13. После изменения спина левого верхнего узла и третьего узла во второй строке получим решетку с энергией 15.

Входные данные

В первой строке входного файла содержатся числа \(N\) и \(M\) (\(1 \leq N, M \leq 1000\), \(N+M > 2\)). Далее следует N строк по M символов в каждой. Строки состоят из символов '+' и '-'. Символ '+' соответствует положительному спину, а '-'  — отрицательному.

Выходные данные
В выходной файл выведите четыре числа: \(r_1\) \(c_1\) \(r_2\) \(c_2\)  — координаты двух узлов, изменение спина в которых максимально увеличит энергию. \(r_i\)  — номер строки узла, \(c_i\)  — номер узла в его строке. Нумерация начинается с 1.
Примеры тестов
Входные данные
3 4
+-+-
-+++
+-+-
Выходные данные
1 1 2 3
Сдать: для сдачи задач необходимо войти в систему