你所耕种的农田由若干块从西向东排列的田地组成。目前，每块田地中都有一定数量的小麦；不同田地间的小麦数量可能不同。所有小麦将在若干天后成熟。

你面临的一个大问题是，每天晚上都有一头饥饿的野猪从西边过来。如果所有田地里都没有小麦了，野猪就会折返。否则，野猪会前往仍然有小麦的最西侧田地，并吃掉那里的一单位小麦。随后，野猪会继续向东移动到相邻的田地并吃掉一单位小麦，直到它遇到一块没有小麦的田地，或者在最东侧的田地吃完小麦，此时它会回家。

为了减轻损失，你计划在今天选择一些田地（可能不选），并移除这些田地里的所有小麦，以便野猪在随后的日子里回来时，吃掉的小麦总量尽可能少。在此之后，野猪仍会每天晚上过来，但你无法再采取任何措施来减轻损失。

给定一个或多个候选收获日。对于每个候选收获日，请确定在该日剩余小麦的最大可能总量，前提是你今天已经最优地选择了要移除小麦的田地。最优的选择方案可能随候选收获日而变化。

输入格式

输入包含单个测试用例，格式如下：

$n$ $m$ $a_1 \dots 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, \dots, n$，整数 $a_i$ 是第 $i$ 块田地中小麦的数量（$0 \le a_i \le 10^{12}$）。对于每个 $j = 1, \dots, m$，整数 $d_j$ 是距离第 $j$ 个候选收获日的天数（$1 \le d_j \le 2 \times 10^{17}$），即野猪在收获日之前会来 $d_j$ 次。

输出格式

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

样例

输入 1

3 4
3 1 4
1
2
3
7

输出 1

6
5
4
0

说明 1

对于样例输入 1，如果你不移除任何小麦，田地中小麦数量的变化如下： $(3, 1, 4) \to (2, 0, 3) \to (1, 0, 3) \to (0, 0, 3) \to (0, 0, 2) \to (0, 0, 1) \to (0, 0, 0)$

相反，如果你移除第 2 块田地的小麦，数量变化如下： $(3, 0, 4) \to (2, 0, 4) \to (1, 0, 4) \to (0, 0, 4) \to (0, 0, 3) \to (0, 0, 2) \to (0, 0, 1) \to (0, 0, 0)$

这种选择对于所有给定的候选收获日都是最优的。

输入 2

6 3
300 200 100 100 200 300
10
50
340

输出 2

1140
1000
560

说明 2

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

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

图 1. 一头野猪