Maximizing Stars in Rotational Sweep

Consider the night sky as a Cartesian plane. Small P is located at the origin \((0,0)\). There are \(n\) stars in the sky; the \(i\)-th star is located at \((x_i,y_i)\). Initially, Small P faces the point \((1,0)\) (i.e. his initial facing direction has an angle of \(0\) radians). Then he will perform \(m\) rotations in place. After the \(i\)-th rotation, he will finish facing in the direction of the point \((u_i,v_i)\).

For each rotation, he is allowed to rotate either counterclockwise or clockwise. During a rotation the facing direction changes continuously; at any moment (including the start and the moment immediately before the rotation stops) he may stop if his current facing direction is such that some stars lie exactly on the ray he is facing.

When small P rotates, he wants to maximize the number of stars that appear exactly in front of him – that is, the stars whose position vector from the origin has the exact same direction (angle) as his current facing direction. Note that if multiple stars lie on the same ray the count is the sum of their occurrences.

Your task is: for each rotation, determine the maximum number of stars that can appear in front of small P during the course of that rotation. After a rotation, his facing direction is updated to the target direction \((u_i,v_i)\), and the next rotation begins from that angle.

Angle details: Let \(\theta\) denote an angle measured in radians. For a star at \((x,y)\), its direction is \(\theta=\mathrm{atan2}(y,x)\). Similarly, for a rotation target \((u,v)\), the target angle is \(\phi=\mathrm{atan2}(v,u)\). For a rotation starting at angle \(\alpha\) and aimed at \(\phi\), if we choose the counterclockwise rotation then the sweep covers the continuous interval of angles from \(\alpha\) to \(\alpha+\Delta\) where \(\Delta= (\phi-\alpha+2\pi) \mod 2\pi\). If we choose clockwise, the sweep covers from \(\alpha\) down to \(\alpha-\left(2\pi-\Delta\right)\). You may choose either direction in order to maximize the number of stars that appear exactly in front of Small P at some moment during the rotation.

Note: Use LaTeX for all formulas. The input values are such that floating point precision issues will not affect correct answers.

inputFormat

The first line contains two integers, \(n\) and \(m\) (number of stars and number of rotations).

The next \(n\) lines each contain two integers \(x_i\) and \(y_i\), the coordinates of the \(i\)-th star.

The following \(m\) lines each contain two integers \(u_i\) and \(v_i\), representing the target point for the \(i\)-th rotation.

outputFormat

Output \(m\) lines. The \(i\)-th line should contain a single integer representing the maximum number of stars that can be observed in front of Small P during the \(i\)-th rotation.

sample

3 2
1 0
0 1
-1 0
1 1
0 -1

1
1