На узагальненій шахівниці (розмірами не обов’язково 8×8) стоїть ферзь. Відомо, на якій клітинці він перебуває зараз, та в яку клітинку йому потрібно дістатись. Задача ускладнюється тим, що деякі клітинки зайняті ворожими фігурами, але спрощується тим, що зараз вони міцно сплять, так що ферзь може тихенько зробити скільки завгодно ходів підряд. Ні перестрибувати через ворожі фігури, ні бити їх не можна (бо тоді вони попросинаються). Напишіть програму, яка знаходитиме мінімальну кількість ходів, необхідних ферзеві для такого переміщення.
Технічні умови. Програма читає з клавіатури розміри шахівниці — спочатку кількість вертикалей w (2 ≤ w ≤ 26), потім кількість горизонталей h (2 ≤ h ≤ 99), потім координати стартової та фінішної клітинок, потім кількість ворожих фігур К (0 ≤ K ≤ w×h–2), далі K пар чисел – координати чергової ворожої фігури. Всі числа розділено пропуском. Координати всіх клітинок – натуральні числа, що не перевищують відповідно w та h. Спочатку вводиться вертикаль, потім горизонталь. Клітинки, вказані як початкова та кінцева, не містять ворожих фігур; різні ворожі фігури не можуть перебувати в одній і тій самій клітинці. Програма має вивести на екран єдине ціле число — або мінімальну кількість ходів, необхідних, щоб дійти від вказаної початкової клітинки до вказаної кінцевої, або -1 на позначення того, що дійти неможливо.