Counting Fence Post Touches

Farmer John has a fence that encloses his field. The fence is made up of P posts connected in order by horizontal or vertical segments, forming a simple rectilinear polygon. The posts have unique coordinates \( (x,y) \) with \(0\le x,y\le 10^9\), and \(P\) is an even number with \(4\le P\le 2\cdot10^5\). The polygon is regular in the sense that every post belongs to exactly two segments and every pair of segments meeting at a post are perpendicular.

There are \(N\) cows \(1\le N\le 10^5\). Each cow takes a daily walk along the fence. Her walk starts at a point on the fence and ends at another point on the fence (these points may lie on an edge or coincide with a post). Because the fence forms a closed loop, there are two possible routes along the fence. Each cow always chooses the shorter route (it is guaranteed that the shorter route is unique, i.e. no tie occurs).

A cow is said to "touch" a fence post if either the post is exactly her starting or ending point, or if she passes by it during her walk. Help Farmer John compute, for each fence post, the total number of times it is touched by any cow during a day.

Note: The positions of the fence posts are given in the order they appear along the fence (either clockwise or counterclockwise), so that the fence forms a closed polygon with the last post connecting back to the first. It is also guaranteed that the fence has a unique structure given these posts.

The fence’s perimeter is defined as the sum of the Manhattan distances between consecutive posts (with the last post connected back to the first). Each point on the fence can be uniquely identified by its distance from the first post along the fence (with distances modulo the total perimeter \(L\)). Each cow’s walking route is then specified by two numbers \(s\) and \(t\) (in the range \([0, L)\)) indicating her starting and ending positions along the fence.

For a cow with starting position \(s\) and ending position \(t\), let \(d = (t - s + L) \bmod L\). If \(s \le t\) then:

• If \(d \le \frac{L}{2}\), the cow walks the arc from \(s\) to \(t\).
• If \(d > \frac{L}{2}\), the cow walks the complementary arc from \(t\) to \(s\) (non–wrapping in the circular sense).

If \(s > t\) then:

• Let \(d = (t - s + L)\). If \(d \le \frac{L}{2}\), the cow walks the arc from \(s\) to \(L) \cup [0, t]\) (a wrapping interval).
• If \(d > \frac{L}{2}\), the cow walks the arc from \(t\) to \(s\).

Any fence post whose position (measured as distance from the first post along the fence) lies on the chosen arc is considered touched by that cow. Your task is to calculate the number of touches for each post.

inputFormat

The first line contains two integers \(P\) and \(N\): the number of fence posts and the number of cows, respectively.

The next \(P\) lines each contain two integers \(x\) and \(y\), representing the coordinates of the fence posts in the order they appear along the fence.

The following \(N\) lines each contain two integers \(s\) and \(t\), representing a cow's starting and ending positions along the fence (measured as a distance from the first post along the fence, in the range \([0, L)\), where \(L\) is the total perimeter of the fence).

outputFormat

Output a single line containing \(P\) integers. The \(i\)-th integer is the number of times the \(i\)-th fence post (in input order) is touched in a day.

sample

4 3
0 0
0 2
2 2
2 0
1 4
7 2
3 0

2 3 1 0