题目描述

$2$ 次元平面上にクリスマスツリーが $N$ 個あり、$i$ 個目のクリスマスツリーは座標 $(x_i,y_i)$ にあります。

以下の $Q$ 個のクエリに答えてください。

クエリ $i$ ： $(a_i,b_i)$ からマンハッタン距離で $K_i$ 番目に近いクリスマスツリーまでの距離はいくつですか？

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $\vdots$ $x_N$ $y_N$ $Q$ $a_1$ $b_1$ $K_1$ $\vdots$ $a_Q$ $b_Q$ $K_Q$

输出格式

$Q$ 行に出力せよ。
$i$ 行目には、クエリ $i$ に対する答えを出力せよ。

题目大意

在平面直角坐标系中有 $N$ 个点，第 $i$ 个点的编号是 $x_i,y_i$。

有 $Q$ 个询问，每个询问给你一个坐标 $a_i,b_i$ 和一个整数 $k_i$，求距离 $a_i,b_i$ 第 $k_i$ 近的点与 $a_i,b_i$ 的距离。

上述的距离指的均是曼哈顿距离。

• $1 \le N \le 10^5$，$1 \le Q \le 10^5$

• $0 \le x_i \le 10^5$，$0 \le y_i \le 10^5$，$1 \le k_i \le N$

• 对于任意两个互不相同的 $i$ 和 $j$，保证 $(x_i,y_i) \neq (x_j,y_j)$

Translated by Tx_Lcy

4
3 3
4 6
7 4
2 5
6
3 5 1
3 5 2
3 5 3
3 5 4
100 200 3
300 200 1

1
2
2
5
293
489

提示

制約

• $1\leq\ N\ \leq\ 10^5$
• $0\leq\ x_i\leq\ 10^5$
• $0\leq\ y_i\leq\ 10^5$
• $i\neq\ j$ ならば $(x_i,y_i)\ \neq\ (x_j,y_j)$
• $1\leq\ Q\ \leq\ 10^5$
• $0\leq\ a_i\leq\ 10^5$
• $0\leq\ b_i\leq\ 10^5$
• $1\leq\ K_i\leq\ N$
• 入力に含まれる値は全て整数である

Sample Explanation 1

$(3,5)$ から $1,2,3,4$ 個目のクリスマスツリーまでのマンハッタン距離は、それぞれ $2,2,5,1$ です。 よって、最初の $4$ つのクエリの答えはそれぞれ $1,2,2,5$ です。