Description

Treat the starry sky as a 2D Cartesian coordinate system. Little P is at $(0,0)$, i.e., the origin. There are $n$ stars in the sky, and the coordinates of the $i$-th star are $(x_i, y_i)$.

Little P initially faces the point $(1,0)$. Then Little P will rotate in place $m$ times. After the $i$-th rotation, he will face the point $(u_i, v_i)$.

He may choose to rotate counterclockwise or clockwise. Once he is facing the final direction of this rotation, the rotation stops immediately.

He believes that, during the rotation, the more stars that appear right in front of him, he [data removed].

Little P wants to know, during each rotation, what is the maximum number of stars that can appear right in front of him (including the stars seen directly in front of him at the initial direction and at the ending direction of the rotation).

Input Format

There are $n + m + 1$ lines in total.

The first line contains two positive integers $n, m$, representing the number of stars and the number of rotations.

The next $n$ lines each contain two integers $x_i, y_i$.

The next $m$ lines each contain two integers $u_i, v_i$, with the meaning described in the Description.

In each line, the two numbers are separated by a single space. The input uses Linux line endings, and there are no extra spaces at the end of any line.

Output Format

Output $m$ lines, each containing one integer. The integer on line $i$ is the answer for the $i$-th rotation.

5 2
1 0
1 1
2 2
-1 2
-2 -1
-1 1
-1 2

4
5

见下发文件 ex_star2.in

见下发文件 ex_star2.out

见下发文件 ex_star3.in

见下发文件 ex_star3.out

Hint

The illustration for Sample 1 is as follows:

Orange points are stars, and the green ray is Little P’s direction during the first rotation. In the first rotation, he turns from $(1,0)$ to $(-1,1)$. If he rotates clockwise (the blue region, including the boundary), the stars on $(1,0)$ and $(-2,-1)$ are counted, for a total of $2$ stars. If he rotates counterclockwise (the green region, including the boundary), the stars on $(1,0)$, $(1,1)$, $(2,2)$, and $(-1,2)$ are counted, for a total of $4$ stars.

In the second rotation, he turns from $(-1,1)$ to $(-1,2)$. Rotating counterclockwise, all $5$ stars will appear right in front of Little P during the rotation.

Except for test points $24$ and $25$, all other test points guarantee that the absolute value of every coordinate is $\le 1000$.

For the first $12$ test points, it is guaranteed that on any ray from the origin to any star, there is no other star.

Except for test points $23$ and $25$, for all test points with odd indices, it is guaranteed that there are no stars on Little P’s initial facing direction and on each target direction.

Except for test points $22$ and $24$, for all test points with even indices, it is guaranteed that there is at least one star on Little P’s initial facing direction and on each target direction.

For $100\%$ of the data, it is guaranteed that all star coordinates are pairwise distinct, no coordinate equals $(0,0)$, and the initial direction of a rotation is never equal to the ending direction.

Sample $3$ satisfies the constraints for even-indexed test points.

Translated by ChatGPT 5