Score : $400$ points

问题描述

你将获得一个包含 $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$ 小的整数。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:18:30