题目描述

平面上有 $n$ 个点。现在有 $m$ 次询问，每次给定一个点 $(px,py)$ 和一个整数 $k$，输出 $n$ 个点中离 $(px,py)$ 的距离第 $k$ 大的点的标号。如果有两个（或多个）点距离 $(px,py)$ 相同，那么认为标号较小的点距离较大。

输入格式

第一行，一个整数 $n$，表示点的个数。
下面 $n$ 行，每行两个整数 $x_i,y_i$，表示 $n$ 个点的坐标。点的标号按照输入顺序，分别为 $1 \dots n$。
下面一行，一个整数 $m$，表示询问个数。
下面 $m$ 行，每行三个整数 $px_{i},{py}_{i},k_{i}$，表示一个询问。

输出格式

$m$ 行，每行一个整数，表示相应的询问的答案。

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

3
1
1

数据规模和约定

$50\%$ 的数据中，$n$ 个点的坐标在某范围内随机分布。
$100\%$ 的数据中，$n \leq 10^5$，$m \leq 10^4$，$1 \leq k \leq 20$，所有点（包括询问的点）的坐标满足绝对值 $\leq 10^9$，$n$ 个点中任意两点坐标不同，$m$ 个询问的点的坐标在某范围内随机分布。