402824: GYM100889 H Hitting Points

In the magical world of felicity, there is a merry go round. This merry go round is in the shape of a convex polygon. The polygon has N points each of which is defined by x and y coordinates. Felicity celebrates a lot of magical festivals, in which any one side of the polygon acts as a magical base, i.e, it lies on the x-axis. This side is denoted by two vertices, p_l and p_r. When the side acts as a magical base, p_l coincides with the origin and p_r lies somewhere else to the right of the origin on the magical base. Unfortunately, there is an infinitely long vertical magical wand, perpendicular to the magical base, that lies at k distance from the origin on the magical base. It is ensured that k > x', where x' is maximum x-coordinate of any polygon vertex. Now this wand falls in counter-clockwise direction till it hits the merry go round.

When the wand hits the merry go round, it generates a flash at the point(s) of collision. Given Q festivals where each is defined by a base, p_l and p_r, and by a k, can you tell what the flash points are?

The first line contains N(3 ≤ N ≤ 10⁵) and Q(1 ≤ Q ≤ 10⁵), the number of points and number of festivals.

The first N lines are the points of the merry go round in counter-clockwise order and each of the lines has two integers x_i and y_i( - 10⁹ ≤ x_i, y_i ≤ 10⁹). Points are indexed from 0 to N - 1 in the order of input.

This is followed by Q lines where each line has two integers and k( and 1 ≤ k ≤ 10⁹). Here denotes p_l of an edge and p_r of that edge is .

Output for each query is the indices of the points that lit up. If the wand collides with only a point, output the index of that point. Else, if it collides with an edge, output the indices of the two vertices where the second vertex lies counter clockwise ahead of the first vertex.

4 1
0 0
1 0
1 1
0 1
0 2

2