• Третий мир
  WORLD

Описание
На тетраэдрической планете в треугольных землях живут существа с 9 пальцами (по три на каждой руке). Сейчас, после создания кораблей, у них возникла проблема поиска оптимального пути между двумя морскими портами. Из-за геометрии их планеты, карты у них треугольные и являются разверткой тетраэдра. Одна из таких карт показана на рисунке (ребра тетраэдра нарисованы жирными линиями). На ней белыми треугольниками обозначена суша. Остальное место занимает вода, по которой может проходить путь. Порты располагаются на воде и обязательно примыкают к суше.



Существуют также рифы (черные точки на рисунке). Рифы могут находиться только в вершинах треугольников. По треугольникам, прилегающим к рифам, путь проходить не может. Известно, что порты не прилегают к рифам.

Система координат у существ следующая: для любого треугольника его первой координатой является число треугольников, расположенных слева от него, а второй - номер ряда, в котором находится данный треугольник. Нумерация рядов производится снизу вверх и начинается с нуля. Риф задается координатами треугольника, в вершине которого он находится. Если треугольник направлен вверх, то риф в верхней вершине, если вниз - то в нижней.

Длиной пути называется число треугольников, по которым проходит путь, включая начальный и конечный треугольники. Путь должен пересекать только стороны соседних треугольников, но не вершины. 

Задача
Напишите программу WORLD, которая определяет длину кратчайшего пути между двумя заданными портами. Один из кратчайших путей между портами A и B показан на карте пунктирной линией.

Входные данные
В первой строке входного файла WORLD.IN записано число N (1<=N<=50) - длина ребра тетраэдра. Во второй - две пары чисел - координаты портов. Третья строка содержит число K - количество клеток суши. В следующие K строк записано по два числа на строку - координаты клеток суши. Далее идет строка, в которой задается число рифов L, а затем L строк описывают координаты рифов.

Выходные данные
В выходной файл WORLD.OUT нужно выдать целое число - длину кратчайшего пути из одного порта в другой. Если такого пути не существует, или длина пути больше 10³, то выдать 0.

Замечание
Все входные и выходные данные представлены в троичной системе счисления


Например:

WORLD.IN
11
102  1  10  11
20
2  0
101  1
102  0
110  0
111  0
2  11
2
2  0
10  10

WORLD.OUT
20