Для тренировки боевых черепах военные построили прямоугольный полигон размером w × h клеток. Некоторые клетки полигона проходимы для черепах, а некоторые — нет. Черепахи могут перемещаться только параллельно сторонам полигона. Полигон сконструирован таким образом, что существует единственный способ добраться от любой проходимой клетки до любой другой проходимой клетки, не проходя при этом по одной и той же клетке дважды. Известно, что черепахи очень быстро бегают по прямой, но испытывают трудности при повороте на 90 градусов. Поэтому сложность маршрута определяется как количество поворотов, которое придётся совершить черепахе при переходе от начальной до конечной клетки маршрута. Вы должны написать программу, вычисляющую сложность маршрута по его начальной и конечной клетке.
Исходные данные
В первой строке через пробел записаны два целых числа h и w, размеры полигона (1 ≤ w · h ≤ 100000). Далее задаётся карта полигона — h строк по w символов в каждой.
Символ «#» обозначает проходимую клетку, а «.» — непроходимую. В (h + 2)-й строке записано целое число q,
количество маршрутов, для которых нужно посчитать сложность (1 ≤ q ≤ 50000). В каждой из следующих q строк через пробел записаны четыре целых числа: номер строки и номер столбца начальной клетки маршрута, номер строки и номер столбца конечной клетки маршрута. Гарантируется, что начальная и конечная клетки маршрута являются проходимыми. Строки занумерованы числами от 1 до h сверху вниз, а столбцы — числами от 1 до w слева направо.
Результат
Для каждого маршрута выведите в отдельной строке единственное число: его сложность.
Пример
исходные данные | результат |
---|
5 4
.#..
###.
..##
.##.
....
4
1 2 2 1
2 3 4 3
4 2 3 4
1 2 4 2 | 1
0
2
3 |
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009