← 返回题目列表

AtCoder · abc418_c

F. 冲水

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

扑克桌上有茶包 N 不同的口味。口味编号为 1 通过 N,并且有 A_i 袋泡茶风味 i (1 \leq i \leq N).

您将使用这些茶袋玩游戏。游戏有一个参数叫 难度 之间 1 和 A_1 + \dots + A_N,包括在内。一场有难度的游戏 b 收益如下:

  1. 你声明一个整数 x。这里,必须满足 b \leq x \leq A_1 + \dots + A_N.
  2. 经销商选择准确 x 从桌子上的茶包中拿出来给你。
  3. 你检查一下味道 x 您收到的茶包,并选择 b 他们的茶袋。
  4. 如果全部 b 你选的茶包味道一样,你赢了。否则,你就输了。

庄家会尽最大努力让你输。

你被给予 Q 疑问,因此逐一回答。的 j第查询如下:

  • 对于难度游戏 B_j,报告最小整数 x 您必须在开始时声明才能保证获胜。如果无法获胜,请报告 -1 代替。

约束

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq B_j \leq \min(10^6, A_1 + \dots + A_N) (1 \leq j \leq Q)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
A_1 \cdots A_N
B_1
\vdots
B_Q

输出

打印 Q 行。

的 j- 第行 (1 \leq j \leq Q)应包含以下问题的答案 j第一个查询。


示例输入 1

4 5
4 1 8 4
1
8
5
2
10

示例输出 1

1
17
14
5
-1

对于 1-st 查询,如果您声明 x=1,那么无论哪一个 1 庄家选择的包,选择合适的即可满足中奖条件 1 包在其中。 因为你不能选择一个整数 x 小于 1,答案是 1.

对于 2-nd 查询,如果您声明 x=17,那么无论哪一个 17 荷官选择的袋子,选择合适的即可满足中奖条件 其中有 8 袋。 相反,如果 x < 17,庄家可以选择袋子来阻止你获胜。 因此,答案是 17.

对于 3-rd 查询,如果您声明 x=14,那么无论哪一个 14 荷官选择的袋子,选择合适的即可满足中奖条件 其中有 5 袋。 相反,如果 x < 14,庄家可以选择袋子来阻止你获胜。 因此,答案是 14.

对于 4-第一个查询,如果您声明 x=5,那么无论哪一个 5 荷官选择的袋子,选择合适的即可满足中奖条件 其中有 2 袋。 相反,如果 x < 5,庄家可以选择袋子来阻止你获胜。 因此,答案是 5.

对于 5第一个查询,无论如何 x 你宣告,庄家可以选择袋子来阻止你获胜。 因此,打印 -1.


示例输入 2

5 3
13 13 13 13 2
5
12
13

示例输出 2

19
47
51