У Вовы есть любимый магнит. Вове очень нравится играть с ним на большой поляне, которую можно представить в виде прямоугольника \(n\) на \(m\) клеток.
Однажды он пришел играть на поляну с магнитом и потерял его в одной из клеток. Вова очень расстроился, но нашел решение — в каждую клетку поляны он положил компас, стрелка которого может принимать 8 положений: вверх, вверх-вправо, вправо, вниз-вправо, вниз, вниз-влево, влево и вверх-влево. Каждому положению стрелки соответствует его номер:
Стрелки принимают направление, близкое к направлению на магнит: если магнит лежит строго по диагонали от компаса, то его стрелка примет диагональное положение, иначе — более близкое к направлению на магнит из вертикального и горизонтального. Стрелка компаса в клетке с магнитом может быть направлена куда угодно.
Рисунок для примера из входных данных, стрелки всех компасов направлены на магнит.
Вова уже был готов к поискам, но тут вспомнил, что на поляне есть аномалия, которая инвертирует показания компасов вдоль ровно одной горизонтали и ровно одной вертикали. У компасов, которые лежат в зоне действия аномалии, стрелка смотрит строго в противоположном направлении тому, в котором она должна указывать.
Рисунок для примера из входных данных с учетом аномалии.
Теперь Вова не знает, как ему найти свой магнит, и просит помощи у вас.
Формат входных данных
В первой строке входных данных записаны два целых числа через пробел \(n\) и \(m\) — размеры поляны (\(2 \le n, m \le 1500, nm \ge 6\)).
В следующих \(n\) строках описываются компасы на поляне.
В \(i\)-й строке записаны \(m\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le 8\)), \(j\)-е число в \(i\)-й строке обозначает направление стрелки компаса в \(j\)-й клетке \(i\)-й строки.
Формат выходных данных
В первой строке выведите два числа \(x\) и \(y\) через пробел — номер строки и столбца клетки, в которой лежит магнит.
Во второй выведите два числа \(a\) и \(b\) через пробел — номера горизонтали и вертикали, в которых действует аномалия.
Замечание
В данном тесте магнит лежит в клетке \((2, 1)\), инвертируется горизонталь номер \(3\) и вертикаль номер \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
5 6 3 7
3 7 3 7
5 4 3 3
|
2 1
3 3
|