/ 
Time Limit: 3 sec / Memory Limit: 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