D - Kth Excluded 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 400

問題文

長さ 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

Score : 400 points

Problem Statement

You are given a sequence of N positive integers: A = (A_1, A_2, \dots, A_N), and Q queries.

In the i-th query (1 \leq i \leq Q), given a positive integer K_i, find the K_i-th smallest integer among the positive integers that differ from all of A_1, A_2, \dots, A_N.

Constraints

  • 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}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the response to the i-th query.


Sample Input 1

4 3
3 5 6 7
2
5
3

Sample Output 1

2
9
4

The positive integers that differ from all of A_1, A_2, \dots, A_N are 1, 2, 4, 8, 9, 10, 11, \dots in ascending order. The second, fifth, and third smallest of them are 2, 9, and 4, respectively.


Sample Input 2

5 2
1 2 3 4 5
1
10

Sample Output 2

6
15