问题描述

在扑克桌上，有 $N$ 种不同口味的茶包，口味编号为 $1$ 到 $N$。第 $i$ 种口味共有 $A_i$ 个茶包。

你将利用这些茶包进行一个游戏。游戏有一个称为难度的参数，其取值范围为 $1$ 到 $\sum_{i=1}^{N}A_i$。

对于难度为 $b$ 的游戏，流程如下：

• 你声明一个整数 $x$，满足 $b\le x\le\sum_{i=1}^{N}A_i$；
• 庄家从所有茶包中任选恰好 $x$ 个交给你；
• 你查看这 $x$ 个茶包，并从中选出恰好 $b$ 个；
• 如果所选出的 $b$ 个茶包全部属于同一种口味，则你获胜；否则失败。

庄家会采用最优策略使你失败。

共有 $Q$ 次询问。对于每次询问，给定难度 $B_j$，请输出为了保证无论庄家如何选择茶包，你都一定能够获胜时，所需声明的最小整数 $x$。如果不存在这样的 $x$，输出 $-1$。

输入格式

第一行输入两个整数 $N,Q$。

第二行输入 $N$ 个整数 $A_1,A_2,\dots,A_N$。

接下来 $Q$ 行，每行输入一个整数 $B_j$，表示一次询问的难度。

输出格式

输出共 $Q$ 行。

对于每个询问，输出对应的最小整数 $x$；如果不存在满足条件的 $x$，输出 $-1$。

样例输入 1

4 5
4 1 8 4
1
8
5
2
10

样例输出 1

1
17
14
5
-1

样例输入 2

5 3
13 13 13 13 2
5
12
13

样例输出 2

19
47
51

说明

对于第一个样例：

• 当难度为 $1$ 时，声明 $x=1$ 即可，因为无论庄家给出哪个茶包，你都可以直接选择它，因此答案为 $1$。

• 当难度为 $8$ 时，声明 $x=17$ 可以保证无论庄家如何选择，你都能够找到同一种口味的 $8$ 个茶包；若 $x<17$，庄家可以选择一种方案使你无法获胜，因此答案为 $17$。

• 当难度为 $5$ 时，答案为 $14$。

• 当难度为 $2$ 时，答案为 $5$。

• 当难度为 $10$ 时，无论声明什么合法的 $x$，庄家都能够使你无法选出同一种口味的 $10$ 个茶包，因此输出 $-1$。

评测数据规模

• $1\le N\le3\times10^5$；
• $1\le Q\le3\times10^5$；
• $1\le A_i\le10^6$；
• $1\le B_j\le\min\left(10^6,\sum_{i=1}^{N}A_i\right)$；
• 所有输入数据均为整数。