题目描述

在二维平面上有 $N$ 个圣诞树，第 $i$ 个树位于坐标$(x_i,y_i)$。

回答以下的 $Q$ 个查询：

第 $i$ 个查询：点$(a_i,b_i)$到最靠近该点的第 $K_i$ 个圣诞树的曼哈顿距离是多少？

约束条件

• $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$
• 输入值都为整数。

输入

从标准输入读入数据，输入的格式如下：

$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$ 个查询的答案。

示例输入 1

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

1
2
2
5
293
489

从点 $(3,5)$ 到该点最靠近的第1个、第2个、第3个和第4个树的距离分别为 1, 2, 2, 5。
因此，前四个查询的答案分别为 1, 2, 2, 5。