Черепахи та повороти
Для тренування бойових черепах військові побудували прямокутний полігон розміром w×h клітинок. Дяекі клітинки полігону проходимі для черепах, а деякі — ні. Черепахи можуть переміщуватись лише паралельно сторонам полігону. Полігон сконструйовано таким чином, що існує єдиний спосіб дістатись від довільної вільної клітинки до довільної іншої вільної клітинки, не проходячи при цьому по одній і тій же клітинці двічі. Відомо, що черепахи дуже швидко бігають по прямій, але у них виникають утруднення при повороті на 90 градусів. Тому складність маршруту визначається як кількість поворотів, які прийдеться здійснити черепасі при переході від початкової до кінцевої клітинки маршруту.
Ви повинні написати програму, яка обчислює складність маршруту за його початковою та кінцевою клітинкам.
Вхідні дані
У першому рядку через пропуск записано два цілих числа h і w, розміри полігону (1 ≤ w·h ≤ 100000). Далі задається карта полігону — h рядків по w символів у кожному. Символ "#" позначає прохідну клітинку, а "." — непрохідну. У (h+2)-й рядку записано ціле число q, кіькість маршрутів, для яких потрібно порахувати складність (1 ≤ q ≤ 50000). У кожному з наступних q рядків через пропуск записано чотири цілих числа: номер рядка та номер стовбця початкової клітинки маршруту, номер рядка та номер стовбця кінцевої клітинки маршруту. Гарантується, що початкова та кінцева клвтинки маршруту є прохідними. Рядки нумеруються числами від 1 до h зверху донизу, а стовбці — числами від 1 до w зліва праворуч.
Вихідні дані
Для кожного маршруту виведіть у окремому рядку єдине число: його складність.