Description

:::epigraph[一头野猪 www.irasutoya.com] :::

你耕种的农田由一定数量的田块组成，这些田块从西向东排列。目前，每个田块都有一定数量的小麦；不同田块的数量可能不同。所有小麦将在一定天数后成熟以待收割。

你面临的一个大问题是，每晚都有一头饥饿的野猪从西边过来。如果所有田块都没有剩下小麦，野猪就会掉头返回。否则，野猪会前往仍然有小麦的最西边的田块，并在那里吃掉一单位小麦。接着，野猪会继续向东移动到相邻的田块并吃掉一单位小麦，直到它遇到一个没有剩余小麦的田块，或者在东边的田块吃完为止，此时它会返回巢穴。

为了减轻损失，你计划今天选择一些田块（可能为零个）并移除这些田块上的所有小麦，这样野猪在随后的日子里可能会因为没东西吃而提前返回。之后，野猪每晚继续前来，但你无法进一步采取措施减轻损失。

你会得到一个或多个候选的收割日。对于每个候选收割日，假设你移除了最优选择的一组田块上的所有小麦，请确定在该日剩余可收割小麦的最大可能数量。对于不同的候选日，最优的田块选择可能不同。

Input Format

输入由单个测试用例组成，格式如下。

$$n \ m$$ $$a_1 \ \cdots \ a_n$$ $$d_1$$ $$\vdots$$ $$d_m$$

整数 $n$ 是田块的数量 ($2 \le n \le 2 \times 10^5$)。田块从西向东编号为 $1$ 到 $n$。整数 $m$ 是候选收割日的数量 ($1 \le m \le 2 \times 10^5$)。对于每个 $i = 1, \ldots, n$，整数 $a_i$ 是田块 $i$ 中的小麦单位数 ($0 \le a_i \le 10^{12}$)。对于每个 $j = 1, \ldots, m$，整数 $d_j$ 是到第 $j$ 个候选收割日的天数 ($1 \le d_j \le 2 \times 10^{17}$)，即在该日之前野猪会来 $d_j$ 次。

Output Format

输出 $m$ 行。第 $j$ 行应包含一个整数，表示第 $j$ 个候选收割日剩余小麦的最大可能单位数。

3 4
3 1 4
1
2
3
7

6
5
4
0

6 3
300 200 100 100 200 300
10
50
340

1140
1000
560

Hint

对于样例输入 1，如果你不移除任何小麦，田块中的小麦数量变化如下。

$$(3, 1, 4) \rightarrow (2, 0, 3) \rightarrow (1, 0, 3) \rightarrow (0, 0, 3) \rightarrow (0, 0, 2) \rightarrow (0, 0, 1) \rightarrow (0, 0, 0)$$

相反，如果你移除田块 2 上的小麦，数量变化如下。

$$(3, 0, 4) \rightarrow (2, 0, 4) \rightarrow (1, 0, 4) \rightarrow (0, 0, 4) \rightarrow (0, 0, 3) \rightarrow (0, 0, 2) \rightarrow (0, 0, 1) \rightarrow (0, 0, 0)$$

对于所有给定的候选日，这个选择都是最优的。

对于样例输入 2，最优选择如下：

• 对于第一个候选日，不移除任何小麦是最优的。剩余数量将是 $(290, 190, 90, 90, 190, 290)$。
• 对于第二个候选日，移除田块 3 上的小麦是最优的。剩余数量将是 $(250, 150, 0, 100, 200, 300)$。
• 对于第三个候选日，移除田块 2 和 4 上的小麦是最优的。剩余数量将是 $(0, 0, 60, 0, 200, 300)$。

翻译由 DeepSeek V3 完成