Гра з фішками
Ви є одним з розробників нової комп'ютерної гри. Гра відбувається на прямокутній дошці, яка складається з W×H клітинок. Кожна клітинка може або містити, або не містити фішку (див. рисунок).
Важливою частиною гри є перевірка того, чи з'єднані дві фішки шляхом, який задовольняє наступні умови:
Шлях повинен складатись з відрізків вертикальних і горизонтальних прямих.
Шлях не повинен перетинати інші фішки.
При цьому частина шляху може виявитись поза дошкою. Наприклад:
Фішки з координатами (1, 3) і (4, 4) можуть бути з'єднані. Фішки з координатами (2, 3) і (5, 3) також можуть бути з'єднані. А ось фішки з координатами (2, 3) і (3, 4) з'єднати не можна – довільни з'єднуючий їх шлях перетинає інші фішки.
Вам необхідно написати програму, яка перевіряє, чи можна з'єднати дві фішки шляхом, який задовільняє вказаним вимогам, і, у випадку позитивної відповіді, яка визначає мінімальну довжину такого шляху (вважається, що шлях має згини, початок і кінець лише у центрах клітинок (або "уявних клітинок", розміщених поза дошкою), а відрізок, яки сполучає центры двох сусідніх клітинок, має довжину 1).
Вхідні дані
Перший рядок вхідного файлу містить два натуральних числа: W – ширина дошки, H – висота дошки (1 ≤ W, H ≤ 75). Наступні H рядків містять опис дошки: кожен рядок складається рівно з W символів: символ "X" (велика англійська літера "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, якщо такого шляху не існує.