Farthest Point Query

Given n points on a plane with labels from 1 to n, and m queries, each query consists of a point (px, py) and an integer k. For each query, you are to determine the k-th largest point by distance from (px, py) among the n points.

Note that if two or more points are at the same distance from (px, py), the point with the smaller label is considered to be farther (i.e. ranked higher in the ordering).

The distance is measured in the Euclidean sense. Two points having the same distance will be ordered so that the one with the smaller index is considered larger.

Ordering:

• Sort all points by distance in descending order.
• If two points have the same distance, the point with the smaller label comes first.

You may use the squared Euclidean distance to avoid floating point issues, i.e., if a point has coordinates (x, y) and the query point is (px, py), then its squared distance is \( (x-px)^2+(y-py)^2 \).

inputFormat

The input is given as follows:

1. The first line contains an integer n \( (1 \leq n \leq 10^5) \), the number of points.
2. Each of the next n lines contains two integers \( x \) and \( y \) \( (-10^9 \leq x, y \leq 10^9) \), representing the coordinates of the points. The points are labeled from 1 to n in the order of input.
3. The next line contains an integer m \( (1 \leq m \leq 10^5) \), the number of queries.
4. Each of the next m lines contains three integers: \( px, py \) and \( k \) \( (1 \leq k \leq n) \), representing the query point and the rank.

outputFormat

For each query, output a single line containing the label (1-indexed) of the point that is the k-th farthest from the query point (px, py) as defined by the ordering above.

sample

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

2
3