Напад на Альфа-Зет#11625
Космічний пірат, капітан Кріс, нещодавно здобув карту штучної, ретельно охоронюваної планети Альфа-Зет, на яку він давно планував здійснити набіг. Виявилося, що вся планета побудована у вигляді двовимірної площини, що складається з модулів, кожен з яких є окремою кімнатою. У кожній парі цілих координат розміщено рівно один модуль розміром 1 \times 1 одиниць. Кожен модуль двосторонньо з’єднаний як мінімум з одним із сусідніх модулів. Більше того, між будь-якими двома модулями існує рівно один шлях. Таким чином, модулі утворюють прямокутний лабіринт без циклів.
На карті капітан Кріс відзначив декілька модулів, які він збирається відвідати — строго в заданому порядку. Що саме він має намір там робити, вас не стосується, але він обіцяв вам цілий статок, якщо ви допоможете визначити, скільки модулів йому доведеться пройти по маршруту (оскільки циклів немає, він завжди обиратиме найкоротший шлях від одного відзначеного модуля до наступного). Перший відзначений модуль вказує на початок його подорожі, останній — на її закінчення.
У першому рядку задано два цілі числа і w~(2 \le h, w \le 1000) — висота і ширина лабіринту.
Далі йдуть h + 1 рядків, що описують лабіринт у форматі ASCII-графіки. Кожен рядок складається з 2 \cdot w + 1 символів. Опис відповідає наступним правилам:
У кожному рядку і стовпці з непарним індексом (починаючи з ) можуть розташовуватися вертикальні стіни або пробіли. Стовпці з парними індексами містять горизонтальні стіни або пробіли.
Перший рядок описує північний кордон лабіринту (завжди складається лише з горизонтальних стін). Кожен наступний рядок описує черговий горизонтальний ряд модулів.
Модуль знаходиться на позиціях з парними індексами стовпців. Його західна і східна стіни розташовані по сусідніх непарних індексах зліва і справа відповідно. Північна стіна розташована в тій же колонці на один рядок вище, а південна — у тій же колонці на один рядок нижче. Якщо стіна відсутня, на її місці стоїть пробіл.
Після опису лабіринту йде одне ціле число m~(2 \le m \le 10^4) — кількість відзначених модулів.
Кожен з наступних рядків містить по два цілі числа і y~(1 \le x \le h, 1 \le y \le w) — координати модуля, який капітан Кріс хоче відвідати. Перша пара координат — початкова точка подорожі, остання — кінцева. Один і той самий модуль може зустрічатися кілька разів, але ніколи підряд два рази і більше. Модуль — це верхній лівий кут лабіринту, а — нижній правий.
Гарантується, що лабіринт є зв'язним. Більше того, між будь-якими двома модулями існує рівно один шлях.
Виведіть одне ціле число — загальну кількість модулів, через які капітан Кріс пройде, якщо буде слідувати маршруту строго в тому порядку, в якому вказані модулі у вхідних даних.
Приклад 1
Приклад 2