問題文

長さ $N$ の正整数列 $A = (A_1, A_2, \\dots, A_N)$ と $Q$ 個のクエリが与えられます。

$i \\, (1 \\leq i \\leq Q)$ 番目のクエリでは、正整数 $K_i$ が与えられるので、$A_1, A_2, \\dots, A_N$ のいずれとも異なる正整数のうち、小さい方から数えて $K_i$ 番目のものを求めてください。

制約

• $1 \\leq N, Q \\leq 10^5$
• $1 \\leq A_1 < A_2 < \\dots < A_N \\leq 10^{18}$
• $1 \\leq K_i \\leq 10^{18}$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $A_1$ $A_2$ $\\ldots$ $A_N$ $K_1$ $K_2$ $\\vdots$ $K_Q$

出力

$Q$ 行出力せよ。$i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。

入力例 1

4 3
3 5 6 7
2
5
3

出力例 1

2
9
4

$3, 5, 6, 7$ のいずれとも異なる正整数を小さい順に並べると $1, 2, 4, 8, 9, 10, 11, \\dots$ となります。 小さい方から $2$ 番目、$5$ 番目、$3$ 番目はそれぞれ $2, 9, 4$ です。

入力例 2

5 2
1 2 3 4 5
1
10

出力例 2

6
15