Рабочее место участника

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из `W`x`H` клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).

Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:

1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.

2. Путь не должен пересекать других фишек.

При этом часть пути может оказаться вне доски. Например:

Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя – любой соединяющий их путь пересекает другие фишки. Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Первая строка входного файла содержит два натуральных числа: `W` – ширина доски, `H` – высота доски (`1\ ≤\ W,\ H\ ≤\ 75`). Следующие `H` строк содержат описание доски: каждая строка состоит ровно из `W` символов: заглавный латинский символ `X` обозначает фишку, символ `.` обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами – `X_1`, `Y_1`, `X_2`, `Y_2`, причём `1\ ≤\ X_1,\ X_2\ ≤\ W`, `1\ ≤\ Y_1,\ Y_2\ ≤\ H`. Здесь `(X_1,\ Y_1)` и `(X_2,\ Y_2)` – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

Для каждого запроса необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует.

5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0

5
6
0