AT_abc440_d [ABC440D] Forbidden List 2

相異なる $ N $ 個の整数からなるリストがあります。リストの $ i $ 個目 ( $ 1 \leq i \leq N $ ) の整数は $ A_i $ です。 $ Q $ 個の質問が与えられるので、それぞれの答えを求めてください。 $ j $ 個目の質問 ( $ 1 \leq j \leq Q $ ) は以下の通りです。 - $ X_j $ 以上の整数であってリストに含まれないもののうち、小さいほうから $ Y_j $ 番目の値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ \cdots $ $ A_N $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 $ j $ 行目 ( $ 1 \leq j \leq Q $ ) には $ j $ 個目の質問の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 個目の質問について、 $ 6 $ 以上の整数であってリストに含まれないもののうち、小さいほうから $ 10 $ 個を挙げると $ 6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17 $ となります。したがって、質問の答えは $ 17 $ です。 $ 2 $ 個目の質問について、 $ 12 $ 以上の整数であってリストに含まれないもののうち、小さいほうから $ 4 $ 個を挙げると $ 12,\ 13,\ 14,\ 15 $ となります。したがって、質問の答えは $ 15 $ です。 $ 3 $ 個目の質問について、 $ 1 $ 以上の整数であってリストに含まれないもののうち、小さいほうから $ 1 $ 番目の値は $ 4 $ です。 $ 4 $ 個目の質問について、 $ 1\,000\,000\,000 $ 以上の整数であってリストに含まれないもののうち、小さいほうから $ 1\,000\,000\,000 $ 番目の値は $ 1\,999\,999\,999 $ です。 ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 1 \leq Q \leq 3 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ A_1, \dots, A_N $ は相異なる - $ 1 \leq X_j \leq 10^9 $ ( $ 1 \leq j \leq Q $ ) - $ 1 \leq Y_j \leq 10^9 $ ( $ 1 \leq j \leq Q $ ) - 入力される値はすべて整数