Problem Background

Note: The time limit and memory limit for this problem are 3 seconds and 512MB, respectively, which are 1.5 times and 2 times the usual limits.

Problem Description

Farmer John has $N$ cows ($1 \le N \le 10^5$) each of whom enjoys walking along the fence surrounding the pasture. Unfortunately, whenever a cow passes a fence post, she bumps into it, requiring Farmer John to periodically repaint the fence posts.

The fence consists of $P$ posts ($4 \le P \le 2 \cdot 10^5$, $P$ is even), each located at a distinct 2D coordinate point $(x, y)$ on FJ's farm map ($0 \le x, y \le 10^9$). Each post is connected to two adjacent posts by a fence segment, either vertical or horizontal, so the entire fence can be seen as a polygon with edges parallel to the $x$-axis or $y$-axis (the last post connects back to the first, ensuring the fence forms a closed loop around the pasture). The fence polygon is "regular" in that fence segments only meet at their endpoints, each post belongs exactly to two fence segments, and every pair of intersecting fence segments at endpoints are perpendicular.

Each cow has a preferred starting and ending position for her daily walk, both being points along the fence (possibly at a post or not). Each cow walks along the fence from her starting position to her ending position. Since the fence forms a closed loop, the cow has two routes to choose from. Being somewhat lazy creatures, each cow chooses the shorter path along the fence. Notably, this choice is always unambiguous—there are no ties!

A cow touches a fence post if she passes it or if it is her starting or ending point. Help FJ calculate the number of touches each fence post experiences daily so he knows which posts to repaint next.

It can be proven that given the positions of all posts, there is only one possible fence configuration.

Input Format

The first line of input contains $N$ and $P$. The next $P$ lines each contain two integers representing the position of a fence post, in no particular order. The next $N$ lines each contain four integers $x_1\ y_1\ x_2\ y_2$, representing the starting position $(x_1, y_1)$ and ending position $(x_2, y_2)$ of a cow.

Output Format

Output $P$ integers, each representing the number of touches a fence post experiences.

Sample Input and Output

Sample Input #1

5 4
3 1
1 5
3 5
1 1
2 1 1 5
1 5 3 4
3 1 3 5
2 1 2 1
3 2 3 3

Sample Output #1

1
2
2
1

Sample Input #2

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

Sample Output #2

1
0
0
0
1
1
1
2

Sample Input #3

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

Sample Output #3

1
1
1
1
1
0
0
0
0
0
0
0

Notes/Hints

Sample Explanation 1

The posts are connected by fence segments as follows:

$$ (3,1) \leftrightarrow (3,5) \leftrightarrow (1,5) \leftrightarrow (1,1) \leftrightarrow (3,1) $$

The cows touch the posts as follows:

1. Posts $2$ and $4$.
2. Posts $2$ and $3$.
3. Posts $1$ and $3$.
4. None.
5. None.

Test Case Properties

• Test cases $4-6$: $N, P \le 1000$.
• Test cases $7-9$: All positions have $0 \le x, y \le 1000$.
• Test cases $10-15$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分