AT_abc364_d [ABC364D] K-th Nearest

[problemUrl]: https://atcoder.jp/contests/abc364/tasks/abc364_d 数直線上に $ N+Q $ 個の点 $ A_1,\dots,A_N,B_1,\dots,B_Q $ があり、点 $ A_i $ の座標は $ a_i $、点 $ B_j $ の座標は $ b_j $ です。 $ j=1,2,\dots,Q $ それぞれについて、以下の問題に答えてください。 - 点 $ A_1,A_2,\dots,A_N $ のうち点 $ B_j $ との距離が $ k_j $ 番目に近い点を $ X $ としたとき、点 $ X $ と点 $ B_j $ との距離を求めよ。 より厳密には、点 $ A_i $ と点 $ B_j $ との距離を $ d_i $ として、$ (d_1,d_2,\dots,d_N) $ を昇順に並び替えてできる列を $ (d_1',d_2',\dots,d_N') $ としたとき、$ d_{k_j}' $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ a_1 $ $ a_2 $ $ \dots $ $ a_N $ $ b_1 $ $ k_1 $ $ b_2 $ $ k_2 $ $ \vdots $ $ b_Q $ $ k_Q $

$ Q $ 行出力せよ。 $ l\ (1\leq\ l\ \leq\ Q) $ 行目には、$ j=l $ としたときの問題に対する答えを整数として出力せよ。

### 制約 - $ 1\leq\ N,Q\ \leq\ 10^5 $ - $ -10^8\leq\ a_i,b_j\ \leq\ 10^8 $ - $ 1\leq\ k_j\leq\ N $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 点 $ A_1,A_2,A_3,A_4 $ と点 $ B_1 $ との距離は順に $ 1,1,7,8 $ なので、点 $ B_1 $ との距離が $ 3 $ 番目に近いのは点 $ A_3 $ です。 よって、点 $ A_3 $ と点 $ B_1 $ との距離である $ 7 $ を出力します。 ### Sample Explanation 2 同じ座標に複数の点がある可能性もあります。