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