LatticeLand

Вхідні дані

Вхідні дані містять одну задачу на кожному рядку вводу. Рядок вводу міститиме послідовність цілих чисел, кожне з яких відокремлене одним пробілом.

Перші два цілі числа будуть $w$ і $h$, ширина і висота сітки. Кожне з цих значень буде між $1$ і $64$, включно. Після цього буде два цілі числа, що представляють координати диска, на якому прокидається LeaperLad. Після цього буде два цілі числа, що представляють координати диска, на якому знаходиться HeloPak. Наступне число буде $f$, кількість стін вогню. Буде шість або менше стін вогню. Після цього буде $f$ наборів з $4$ цілих чисел, що представляють дві координати кінцевих точок стін.

Для всіх координат, перше число буде між $0$ і w-1, включно, а друге число буде між $0$ і h-1, включно. Усі стіни вогню будуть принаймні однієї одиниці довжини. HeloPak і LeaperLad ніколи не починають на одному диску, і жоден з них не починає на диску, що знаходиться на стіні вогню. Завжди буде спосіб для LeaperLad дістатися до свого HeloPak.

Буде не більше 50 задач.

Вихідні дані

Для кожного рядка вводу, виведіть одне ціле число, що вказує мінімальну кількість ходів, необхідних для того, щоб LeaperLad дістався до свого HeloPak. Зверніть особливу увагу на перші кілька прикладів; вони пояснюють, як рахуються ходи.

Приклади

Приклад 1

2 1 0 0 1 0 0

Це вимагає двох ходів. У першому ході LeaperLad прискорюється на одну одиницю в позитивному напрямку $x$ і стрибає на диск призначення. У другому ході він уповільнюється до необхідної швидкості нуль (зверніть увагу, що хоча позиція LeaperLad не змінюється під час другого ходу, це все одно враховується в загальній кількості).

Приклад 2

2 2 0 0 1 1 0

Це вимагає чотирьох ходів. LeaperLad спочатку рухається вправо, як у попередньому прикладі, але він повинен спочатку уповільнитися в напрямку $x$, потім прискоритися в напрямку $y$, щоб стрибнути вниз, потім знову уповільнитися, щоб стати нерухомим.

Приклад 3

4 2 1 0 2 1 2 0 1 1 1 2 0 3 0

Це вимагає восьми ходів. LeaperLad не може стрибнути по діагоналі з місця; йому потрібно відступити, щоб набрати імпульс спочатку. Тому спочатку він повинен переміститися в позицію $(0,0)$, потім уповільнитися, щоб розвернутися, потім прискоритися в напрямку $x$, стрибаючи на своє початкове місце. Його імпульс дозволяє йому прискоритися в напрямку $y$, щоб зробити діагональний рух. Після приземлення на місце призначення, у нього є одна одиниця імпульсу в обох напрямках $x$ і $y$, тому він повинен уповільнитися, спочатку в напрямку $y$ (що переносить його в позицію $(3,1)$, перевищуючи місце призначення). Потім він уповільнюється, щоб розвернутися, стрибає на місце призначення ще раз і потім уповільнюється, щоб стати нерухомим, всього вісім ходів.

Приклад 4

9 9 8 3 8 5 4 8 4 5 1 5 1 2 4 2 4 5 7 5 7 8 4

Це вимагає $16$ ходів.

Приклад 5

9 9 2 2 7 8 6 0 6 4 3 6 8 3 7 1 7 4 1 3 6 7 0 4 1 1 2 5 7 6 3

Це вимагає $43$ ходів.

Приклади