Каждая из \(N\) коров (\(1 \leq N \leq 10^5\)) Фермера Джона любит
ежедневно прогуливаться вдоль изгороди вокруг пастбища.
Изгородь состоит из \(P\) столбов (\(4 \leq P \leq 2\cdot 10^5\), \(P\) чётное),
расположение каждого из них имеет координаты \((x,y)\) на карте фермы
(\(0 \leq x, y \leq 1000\)). Каждый столб соединяется с двумя соседними
столбами либо горизонтальным, либо вертикальным отрезком. Таким образом
вся изгородь может рассматриваться как многоугольник стороны которого
параллельны осям координат x или y. Последний столб соединён с первым,
поэтому получается замкнутый многоугольник вокруг пастбища.
Отрезки изгороди могут пересекаться только в конечных точках, каждый столб
принадлежит ровно двум конечным точкам отрезков, и каждые два отрезка,
которые имеют общую точку, перпендикулярны.
Каждая корова имеет предпочтительные стартовую и конечную позиции прогулки,
которые являются точками где-то вдоль изгороди (возможно в столбе, возможно нет)
Каждая корова совершает свою ежедневную прогулку начиная со своей стартовой
позиции и заканчивая в своей конечной позиции. Имеется два маршрута, которые
корова может выбрать, поскольку изгородь представляет замкнуты цикл.
Поскольку коровы ленивы, каждая корова идёт вдоль изгороди в направлении,
которое обеспечивает кратчайший путь из начальной точки в конечную.
Если оба пути одинаковы, корова может выбрать любое направлении.
Определите расстояние, которое пройдёт каждая корова.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\) и \(P\). Каждая из последующих \(P\) строк
содержит два целых числа, представляющих позиции столбов изгороди в порядке
её обхода по часовой стрелке или против часовой стрелки. Каждая из последующих
\(N\) строк содержит 4 целых числа \(x_1\) \(y_1\) \(x_2\) \(y_2\) представляющих
стартовую позицию \((x_1, y_1)\) и конечную позицию \((x_2, y_2)\) каждой коровы.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N\) целых чисел, задающих расстояние, которое пройдёт каждая корова.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0
|
2
3
3
4
4
|