AT_abc418_c [ABC418C] Flush

ポーカーテーブルの上に $ N $ 種類のフレーバーのティーバッグが置かれています。フレーバーには $ 1 $ から $ N $ までの番号が付けられており、フレーバー $ i $ ( $ 1 \leq i \leq N $ ) のティーバッグは $ A_i $ 個あります。 あなたはこれらのティーバッグを使ったゲームに参加します。ゲームには $ 1 $ 以上 $ A_1 + \dots + A_N $ 以下の**難易度**が設定されており，難易度 $ b $ のゲームは以下の流れで行われます。 1. あなたは整数 $ x $ を宣言する。このとき、 $ b \leq x \leq A_1 + \dots + A_N $ を満たす必要がある。 2. ディーラーはポーカーテーブルの上にあるティーバッグの中からちょうど $ x $ 個を選び、あなたに渡す。 3. あなたは渡された $ x $ 個のティーバッグのフレーバーを確認し、その中から $ b $ 個のティーバッグを選ぶ。 4. あなたが選んだ $ b $ 個のティーバッグがすべて同じフレーバーであれば、あなたは勝利する。そうでなければ、あなたは敗北する。 ディーラーはあなたが敗北するように最善を尽くすものとします。 $ Q $ 個の質問が与えられるので、それぞれに答えてください。 $ j $ 番目の質問は以下の通りです。 - 難易度 $ B_j $ のゲームに勝利するためにはじめに宣言する必要がある整数 $ x $ の最小値を答えよ。勝利が不可能であれば、代わりに $ -1 $ と答えよ。

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

$ Q $ 行出力せよ。 $ j $ 行目 ( $ 1 \leq j \leq Q $ ) には、 $ j $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリにおいて、 $ x=1 $ を宣言すれば、ディーラーがどの $ 1 $ 個のティーバッグを選んで渡しても、その中から適切に $ 1 $ 個を選ぶことで勝利条件を満たすことが可能です。 $ 1 $ より小さい整数を $ x $ として宣言することはできないので、答えは $ 1 $ です。 $ 2 $ 番目のクエリにおいて、 $ x=17 $ を宣言すれば、ディーラーがどの $ 17 $ 個のティーバッグを選んで渡しても、その中から適切に $ 8 $ 個を選ぶことで勝利条件を満たすことが可能です。 逆に $ x < 17 $ のとき、ディーラーはあなたを敗北させるようにティーバッグを選んで渡すことが可能です。したがって、答えは $ 17 $ です。 $ 3 $ 番目のクエリにおいて、 $ x=14 $ を宣言すれば、ディーラーがどの $ 14 $ 個のティーバッグを選んで渡しても、その中から適切に $ 5 $ 個を選ぶことで勝利条件を満たすことが可能です。 逆に $ x < 14 $ のとき、ディーラーはあなたを敗北させるようにティーバッグを選んで渡すことが可能です。したがって、答えは $ 14 $ です。 $ 4 $ 番目のクエリにおいて、 $ x=5 $ を宣言すれば、ディーラーがどの $ 5 $ 個のティーバッグを選んで渡しても、その中から適切に $ 2 $ 個を選ぶことで勝利条件を満たすことが可能です。 逆に $ x < 5 $ のとき、ディーラーはあなたを敗北させるようにティーバッグを選んで渡すことが可能です。したがって、答えは $ 5 $ です。 $ 5 $ 番目のクエリにおいて、どのように $ x $ を宣言しても、ディーラーはあなたを敗北させるようにティーバッグを選んで渡すことが可能です。したがって、 $ -1 $ を出力します。 ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 1 \leq Q \leq 3 \times 10^5 $ - $ 1 \leq A_i \leq 10^6 $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq B_j \leq \min(10^6, A_1 + \dots + A_N) $ ( $ 1 \leq j \leq Q $ ) - 入力される値は全て整数である。