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

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Формат входного файла

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

Формат выходного файла

В выходной файл выведите четыре числа: r1 c1 r2 c2  — координаты двух узлов, изменение спина в которых максимально увеличит энергию. ri  — номер строки узла, ci  — номер узла в его строке. Нумерация начинается с 1.

Ограничения

1 ≤ N, M ≤ 1000; N + M > 2;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
+-+-
-+++
+-+-
1 1 2 3

0.133s 0.031s 15