Никите на день рождения подарили набор для создания слаймов. Обрадовавшись подарку, Никита сделал квадратного слайма, и положил его на стол. Слайм, испугавшись предстоящих экспериментов Никиты, решил от него сбежать.
Стол представляет собой прямоугольное поле из $$$n$$$ строк и $$$m$$$ столбцов. В некоторых клетках стола находятся дырки, если хотя бы одна клетка слайма окажется на дырке, он упадет со стола. Слайм занимает 4 клетки, и изначально находится в верхнем левом углу поля размером $$$2 \times 2$$$, цель его побега — занять нижний правый угол размером $$$2 \times 2$$$.
Слайм может передвигаться по полю с помощью трансформаций. Трансформация заключается в следующем: одна из клеток слайма передвигается в другую, соседнюю с ней по стороне или углу. После трансформации слайм должен образовывать 4-связную фигуру (иными словами, между любыми двумя клетками слайма должен существовать путь по клеткам слайма, переходящий каждый раз в клетку, соседнюю по стороне).
Слайм хочет сбежать от Никиты как можно быстрее, чтобы его клетки никогда не оказывались на клетках стола с дырками. Найдите минимальное число трансформаций, за которое он сможет это сделать.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 3 \cdot 10^5$$$; $$$n \cdot m \le 3 \cdot 10^5$$$) — размеры стола.
В следующих $$$n$$$ строках содержатся по $$$m$$$ символов $$$a_{i, j}$$$ — описание стола. Символ «#» обозначает дырку в столе, а символ «.» обозначает поверхность стола.
Гарантируется, что верхний левый и нижний правый углы стола размером $$$2 \times 2$$$ составляют поверхность стола.
Выведите минимальное количество трансформаций, в результате которых слайм займет нижний правый угол стола размером $$$2 \times 2$$$, начав в верхнем левом, либо $$$-1$$$, если он не сможет этого сделать.
3 3..#...#..
5
3 5..###.....##...
-1
На рисунке приведены трансформации для первого примера. Черным обозначены дырки в столе, серым — клетки слайма. Стрелками обозначены передвижения клеток.
