Description

There are $n$ points on the plane. There are $m$ queries. In each query, given a point $(px, py)$ and an integer $k$, output the index of the $k$-th farthest point from $(px, py)$ among the $n$ points. If two (or more) points have the same distance to $(px, py)$, then the point with the smaller index is considered farther.

Input Format

The first line contains an integer $n$, the number of points. The next $n$ lines each contain two integers $x_i, y_i$, the coordinates of the $n$ points. The indices of the points follow the input order and are $1\ldots n$. The next line contains an integer $m$, the number of queries. The next $m$ lines each contain three integers $px_i, py_i, k_i$, describing a query.

Output Format

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

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

3
1
1

Hint

• Constraints and Notes.
  • In $50\%$ of the testdata, the coordinates of the $n$ points are randomly distributed within some range.
  • In $100\%$ of the testdata, $1\le n\le 10^5$, $1\le m\le 10^4$, $1\le k\le 20$, $-10^9\le x_i, y_i, px_i, py_i\le 10^9$. Any two points among the $n$ points have different coordinates. The coordinates of the query points in the $m$ queries are randomly distributed within some range.

Translated by ChatGPT 5