曼哈顿圣诞树

题目描述

二维平面上有 $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$ 的答案。

样例

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

从 $(3,5)$ 到第 $1$、第 $2$、第 $3$、第 $4$ 棵圣诞树的曼哈顿距离分别是 $2$、$2$、$5$、$1$。

因此,前四个查询的答案分别是 $1$、$2$、$2$、$5$。

数据范围

• $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$
• 输入中的所有值均为整数