P1131

JZPFAR

平面上有 nn 个点，按照输入顺序编号为 11 到 nn。

现在有 mm 次询问。每次询问给定一个点 (px,py)(p_x,p_y) 和一个整数 kk，请输出给定的 nn 个点中，与 (px,py)(p_x,p_y) 的距离第 kk 大的点的编号。

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

输入格式

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

接下来 nn 行，每行输入两个整数 xi,yix_i,y_i，表示第 ii 个点的坐标。

下一行输入一个整数 mm，表示询问的个数。

接下来 mm 行，每行输入三个整数 pxi,pyi,kipx_i,py_i,k_i，表示一次询问。

输出格式

输出共 mm 行，每行一个整数，表示对应询问的答案。

样例输入

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

样例输出

3
1
1

数据范围

  • 1≤n≤1051\le n\le 10^5；
  • 1≤m≤1041\le m\le 10^4；
  • −109≤xi,yi,pxi,pyi≤109-10^9\le x_i,y_i,px_i,py_i\le 10^9；
  • 1≤ki≤min⁡(n,20)1\le k_i\le \min(n,20)。

来源与许可

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