울타리를 따라 걷기

Farmer John의 소 $N$마리($1 \leq N \leq 10^5$)는 각자 매일 목장을 둘러싼 울타리를 따라 산책하기를 좋아한다.

울타리는 $P$개의 기둥($4 \leq P \leq 2\cdot 10^5$, $P$는 짝수)으로 이루어진다. 각 기둥은 FJ 농장 지도 위의 서로 다른 2차원 점 $(x,y)$이다($0 \leq x, y \leq 1000$). 각 기둥은 인접한 두 기둥과 수직 또는 수평 선분으로 연결된다. 따라서 울타리는 변이 x축 또는 y축과 평행한 다각형이다. 마지막 기둥은 첫 기둥과 연결되어 울타리가 목장을 감싸는 닫힌 고리를 이룬다. 울타리 선분은 끝점에서만 겹치며, 각 기둥은 선분 끝점 두 개와 정확히 맞닿는다. 끝점에서 만나는 두 선분은 항상 서로 수직이다.

각 소는 산책할 때 시작 위치와 도착 위치를 미리 정해 둔다. 각 위치는 울타리 위의 점이며, 기둥 위에 있을 수도 있고 아닐 수도 있다. 소는 시작 위치에서 도착 위치까지 울타리를 따라 걷는다. 울타리는 닫힌 고리이므로 경로는 두 가지가 가능하다. 소는 게을러서 더 짧은 쪽으로 걷는다(두 경로의 길이가 같으면 어느 쪽을 택해도 된다). 각 소가 걷는 거리를 구하라.

첫 줄에 $N$과 $P$가 주어진다. 이어지는 $P$개의 줄에는 기둥의 좌표가 시계 방향 또는 반시계 방향 순서로 한 줄에 정수 두 개씩 주어진다. 이어지는 $N$개의 줄에는 각 소의 시작 위치 $(x_1, y_1)$과 도착 위치 $(x_2, y_2)$를 나타내는 정수 네 개 $x_1$ $y_1$ $x_2$ $y_2$가 주어진다.

각 소가 걷는 거리를 한 줄에 하나씩 $N$개의 정수로 출력하라.