Shortest Walk on the Fence

Farmer John's $N$ cows ($1 \le N \le 10^5$) love to take a walk along the fence surrounding his pasture. The fence is a closed polygon with $P$ posts ($4 \le P \le 2\cdot10^5$, $P$ even), where each post is given by a unique coordinate $(x,y)$ with $0 \le x,y \le 1000$. Consecutive posts are connected by segments that are either horizontal or vertical, and the polygon is simple, meaning that the segments only intersect at their endpoints (with each intersection being perpendicular). Each cow has a preferred starting and ending point on the fence (which may lie exactly at a post or somewhere along a segment). Since the fence forms a closed loop, there are two possible routes between the two points. A cow will always choose the shorter route (if both are equal, either may be chosen). Your task is to determine the distance each cow walks along the fence.

inputFormat

The input begins with a line containing two integers $N$ and $P$.

The next $P$ lines each contain two integers $x$ and $y$, which give the coordinates of the fence posts in the order they appear along the fence (the $P$th post is connected back to the first).

This is followed by $N$ lines, each containing four integers $x_1$, $y_1$, $x_2$, $y_2$. These represent the starting and ending points on the fence for a cow. It is guaranteed that these points lie on the fence.

outputFormat

For each cow, output a single line with the length of the shorter path along the fence from the starting point to the ending point.

sample

3 4
0 0
0 10
10 10
10 0
0 0 10 10
0 5 10 5
0 10 10 0

20
20
20