AT_abc233_h [ABC233Ex] Manhattan Christmas Tree

[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 $ に対する答えを出力せよ。

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