题目描述

给定一个长度为 $N$ 的正整数有序序列 $A=(A_1,A_2,…,A_N)$ 和 $Q$ 个查询。在第 $i$ 个查询中（$1≤i≤Q$），给定一个正整数 $K_i$，要求找出与所有 $A_1,A_2,…,A_N$ 不同的正整数中，按从小到大的顺序第 $K_i$个的数。

输入格式

输入以以下格式从标准输入给出：

$N \ Q$
$A_1 \ A _2 \ … \ A_N$
$K_1$
$K_2$
$⋮$
$K_Q$

输出格式

输出 $Q$ 行。第 $i$行应为第 $i$ 个查询的结果。

样例

4 3
3 5 6 7
2
5
3

2
9
4

5 2
1 2 3 4 5
1
10

6
15

样例1解释

与所有$A_1,A_2,…,A_N$ 不同的正整数按升序排列为$1,2,4,8,9,10,11,…。$ 其中第二、第五和第三小的数分别为$2、9$和$4$

数据范围

• $1≤N,Q≤10^5$
• $1≤A_1<A_2<⋯<A_N≤10^{18}$
• $1≤K_i≤10^{18}$
• 输入中的所有值均为整数。

来源

• AtCoder ABC205D