[ABC233Ex] Manhattan Christmas Tree

在平面直角坐标系中有 $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](https://www.luogu.com.cn/user/253608)

[problemUrl]: https://atcoder.jp/contests/abc233/tasks/abc233_h $ 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 $ に対する答えを出力せよ。

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 $ です。