AT_abc233_h [ABC233Ex] Manhattan Christmas Tree

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

### 限制条件 - $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$ - 输入中的所有值均为整数 ### 样例解释 1 从 $(3,5)$ 到第 $1,2,3,4$ 棵圣诞树的曼哈顿距离分别为 $2,2,5,1$。 因此，前 $4$ 个查询的答案分别为 $1,2,2,5$。 由 ChatGPT 4.1 翻译