Напад на Альфа-Зет

Космічний пірат капітан Кріс нещодавно придбав карту штучної та високо захищеної планети Альфа-Зет, на яку він давно планував здійснити набіг. Виявляється, вся планета побудована на 2D-площині з модулями, кожен з яких служить однією кімнатою. У кожній парі цілих координат є рівно один модуль, а розмір модулів становить рівно $1\times 1$ одиниць. Кожен модуль двонаправлено з'єднаний як мінімум з одним сусіднім модулем. Крім того, для будь-яких двох модулів існує рівно один шлях між ними. Загалом модулі утворюють прямокутний лабіринт без петель.

На карті капітан Кріс відзначив кілька модулів, які він хоче відвідати, саме в зазначеному порядку. Те, що він збирається там робити, не ваша справа, але він обіцяє вам цілий статок, якщо ви визначите кількість модулів, які йому доведеться пройти по маршруту (оскільки петель немає, він завжди обере прямий шлях від одного відзначеного модуля до наступного). Перший відзначений модуль вказує, де він починає свою подорож, останній — де він хоче закінчити.

Вхідні дані

У першому рядку задано два цілі числа $h$ та $w(2\le h,w\le 1000)$ — висота та ширина лабіринту.

Далі йдуть $h+1$ рядок, що описують лабіринт в ASCII форматі, кожен рядок містить $2\cdot w+1$ символів. Опис завжди слідує таким правилам:

• У кожному рядку та стовпці з непарним індексом (починаючи з індексу $1$) стоять або вертикальні стіни, або пробіли, а стовпці з парним індексом містять або горизонтальні стіни, або пробіли.

• Перший рядок описує північну стіну лабіринту (яка завжди складається тільки з горизонтальних стін). Кожен наступний рядок описує рядок модулів.

• Модуль розташований у кожному парному індексі стовпця. Його західна та східна стіни розташовані по безпосередньо сусідніх індексах непарних стовпців відповідно, північна стіна розташована по тому ж індексу стовпця, але на один рядок вище, а південна стіна знаходиться на своєму місці. Якщо стіна відсутня, відповідна позиція замість неї містить пробіл.

Після опису лабіринту дано ціле число $m(2\le m\le 10^4)$.

Кожен з наступних $m$ рядків описує відзначений модуль з двома цілими координатами $x$ та $y(1\le x\le h,1\le y\le w)$. Перша пара координат — це початкова точка подорожі, остання пара — кінцева точка. Модулі можуть з'являтися кілька разів, але ніколи двічі і більше підряд. $(1,1)$ — верхній лівий модуль, а $(h,w)$ — нижній правий модуль.

Гарантовано, що сам лабіринт замкнутий. Більше того, гарантовано, що між будь-якими двома модулями існує рівно один шлях.

Вихідні дані

Виведіть одне ціле число — кількість модулів, які капітану Крісу доведеться пройти, якщо він буде слідувати по маршруту в точному порядку, зазначеному у вхідних даних.

Приклади