F. Препятствующая полоса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вышедший на пенсию бегун Усейн Олд решил в качестве утренней тренировки пройти полосу препятствий. Полоса представляет из себя последовательность из $$$n$$$ столбиков различной целой высоты. В каждый момент времени Усейн находится на каком-то из столбиков и может переместиться только на соседний с ним.

Усейн уже не молод, поэтому не хочет повредить суставы при прохождении полосы. Перемещение со столбика высоты $$$h$$$ на соседний называется безопасным, если его высота находится между $$$h - 3$$$ и $$$h + 2$$$ включительно. Если высота нового столбика хотя бы на $$$4$$$ ниже, то при прыжке есть риск повредить ноги, а если хотя бы на $$$3$$$ выше — при подъеме можно повредить руки. Также обратите внимание на то, что Усейн может двигаться как в правую, так и в левую сторону.

Помогите Усейну найти наиболее длинный участок полосы препятствий, который он может безопасно преодолеть. А именно, подберите пару чисел $$$s, t$$$ с максимальным $$$|s - t|$$$, чтобы Усейн мог добраться от $$$s$$$-го столбика до $$$t$$$-го, производя лишь безопасные перемещения.

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

В первой строке ввода через пробел заданы два целых числа $$$m$$$ и $$$n$$$ — количество следующих строк во вводе и количество столбиков ($$$1 \leqslant n, m \leqslant n \cdot m \leqslant 10^6$$$).

Следующие $$$m$$$ строк задают полосу препятствий в виде матрицы размера $$$m \times n$$$. Каждая строка имеет длину $$$n$$$ и состоит из символов «.» и «#». Символ «.» означает, что данная клетка ничем не занята, а «#» — что эта клетка занята столбиком. Все столбики начинаются от уровня земли. Таким образом, если в $$$i$$$-й строке на $$$j$$$-м месте стоит решетка, то и во всех следующих строках на этой позиции будет находиться решетка. Высота каждого столбика задается количеством решеток в соответствующем столбце матрицы.

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

Выведите через пробел два целых числа $$$s$$$ и $$$t$$$, обозначающих границы движения Усейна по полосе. Обратите внимание, что направление движения имеет значение, и ответы «s t» и «t s» отличаются.

Примеры
Входные данные
5 7
#......
#....#.
#...##.
##..###
#######
Выходные данные
1 7
Входные данные
8 6
......
#...#.
#.#.#.
#.#.#.
#.#.#.
#.#.##
###.##
######
Выходные данные
1 1
Примечание

В первом примере ответ «1 7» единственный верный. При $$$s=2$$$, $$$t=7$$$ Усейн всё ещё сможет добраться от старта до финиша, но это не два самых далёких столбика, между которыми он сумеет переместиться. При $$$s=7$$$, $$$t=1$$$ Усейну нужно будет перебраться со второго столбика на первый, что небезопасно.

Во втором примере между всеми парами столбиков слишком большие перепады высот, поэтому оптимально будет оставаться на месте на любом столбике.