分数: 500 点
问题陈述
有 N 卡。的 i第一张卡有一个整数 上面写着 A_i 。 对于任意两张牌,这些牌上的整数都是不同的。
使用这些卡,高桥和青木将玩以下游戏:
- 青木选择一个整数 x.
- 从高桥开始,两名玩家轮流拿一张牌。应按以下方式选择卡:
- 高桥应该拿剩余卡中整数最大的卡。
- Aoki 应该拿下整数最接近的牌 剩余卡中的 x 。如果有多张这样的牌,他应该拿这些牌中整数最小的牌。
- 当没有剩余牌时游戏结束。
你被给予 Q 候选人的价值 x: X_1, X_2, ..., X_Q。 对于每个 i (1 \leq i \leq Q),找到如果青木选择,高桥将拿走的卡片上写的整数的总和 x = X_i.
约束
- 2 \leq N \leq 100 000
- 1 \leq Q \leq 100 000
- 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
- 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 ... A_N X_1 X_2 : X_Q
输出
打印 Q 行。的 i- 第行 (1 \leq i \leq Q)应包含以下问题的答案 x = X_i.
示例输入 1
5 5 3 5 7 11 13 1 4 9 10 13
示例输出 1
31 31 27 23 23
例如,当 x = X_3(= 9),游戏进行如下:
- 高桥拿着卡片 13.
- 青木拿牌 7.
- 高桥拿着卡片 11.
- 青木拿牌 5.
- 高桥拿着卡片 3.
因此, 13 + 11 + 3 = 27 应打印在第三行。
示例输入 2
4 3 10 20 30 40 2 34 34
示例输出 2
70 60 60