JZPFAR

平面上有 $n$ 个点，按照输入顺序编号为 $1$ 到 $n$。

现在有 $m$ 次询问。每次询问给定一个点 $(p_x,p_y)$ 和一个整数 $k$，请输出给定的 $n$ 个点中，与 $(p_x,p_y)$ 的距离第 $k$ 大的点的编号。

若两个或多个点与 $(p_x,p_y)$ 的距离相同，则认为编号较小的点距离更大。

输入格式

第一行输入一个整数 $n$，表示点的个数。

接下来 $n$ 行，每行输入两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

下一行输入一个整数 $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

数据范围

• $1\le n\le 10^5$；
• $1\le m\le 10^4$；
• $-10^9\le x_i,y_i,px_i,py_i\le 10^9$；
• $1\le k_i\le \min(n,20)$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

3
1
1