Walking Along a Fence

Farmer John's $N$ cows ($1 \leq N \leq 10^5$) each like to take a daily walk around the fence enclosing his pasture.

The fence consists of $P$ posts ($4 \leq P \leq 2\cdot 10^5$, $P$ even). Each post is a different 2D point $(x,y)$ on a map of FJ's farm ($0 \leq x, y \leq 1000$). Each post connects to the two adjacent posts by fence segments that are either vertical or horizontal, so the fence is a polygon whose sides are parallel to the x or y axes. The last post connects back to the first post, so the fence forms a closed loop that encloses the pasture. Fence segments overlap only at their endpoints, each post matches exactly two segment endpoints, and every two segments that meet at an endpoint are perpendicular.

Each cow has a preferred starting position and ending position for her walk. Each position is a point somewhere on the fence, possibly at a post and possibly not. The cow walks along the fence from her starting position to her ending position. Because the fence is a closed loop, there are two possible routes. Cows are lazy, so each cow takes the shorter route (if the two routes tie, the cow may choose either one). Determine the distance each cow walks.

The first line contains $N$ and $P$. Each of the next $P$ lines contains two integers, the coordinates of a fence post, listed in clockwise or counterclockwise order. Each of the next $N$ lines contains four integers $x_1$ $y_1$ $x_2$ $y_2$, the starting position $(x_1, y_1)$ and the ending position $(x_2, y_2)$ of a cow.

Write $N$ integers, one per line, giving the distance each cow walks.