[国家集训队]JZPFAR

题目背景

原《零件分组》见 P1233。

题目描述

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

输入输出格式

输入格式


第一行,一个整数 $n$,表示点的个数。 下面 $n$ 行,每行两个整数 $x_i,y_i$,表示 $n$ 个点的坐标。点的标号按照输入顺序,分别为 $1\ldots n$。 下面一行,一个整数 $m$,表示询问个数。 下面 $m$ 行,每行三个整数 $px_i,py_i,k_i$,表示一个询问。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3
1
1

说明

#### 数据规模与约定 - $50\%$ 的数据中,$n$ 个点的坐标在某范围内随机分布。 - $100\%$ 的数据中,$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$,$n$ 个点中任意两点坐标不同,$m$ 个询问的点的坐标在某范围内随机分布。