Painting Fence Posts

Farmer John's $N$ cows ($1 \leq N \leq 10^5$) each like to take a daily walk around the fence that encloses his pasture. Whenever a cow walks past a fence post, she brushes against it, so Farmer John has to repaint the posts regularly.

The fence has $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 the farm ($0 \leq x, y \leq 10^9$). Each post connects to the two adjacent posts by a fence segment that is either vertical or horizontal, so the fence is a polygon whose sides are parallel to the x or y axis. The last post connects back to the first post, forming a closed loop around the pasture. Fence segments overlap only at their endpoints. Each post is the endpoint of exactly two fence segments, and any two segments that meet at an endpoint are perpendicular. Given the post locations, the fence is uniquely determined.

Each cow has a preferred starting point and ending point on the fence. These may be at posts or between posts. A cow walks from her start to her end along the fence. Since the fence is a closed loop, there are two possible routes, and each cow takes the shorter one. There are never ties.

A cow touches a post if she walks past it, or if the post is her start or end point. Compute the number of daily touches each post receives, so Farmer John knows which post to repaint next.

The first line contains $N$ and $P$. Each of the next $P$ lines contains two integers, the position $(x, y)$ of a fence post. The posts are listed in no particular order. Each of the next $N$ lines contains four integers $x_1$ $y_1$ $x_2$ $y_2$, the start $(x_1, y_1)$ and end $(x_2, y_2)$ of one cow's walk.

Print $P$ integers, the number of touches received by each fence post.