Helloooo! Can you hear me?

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$，其中每个元素均大于或等于 $-1$。使用该序列和一个参数 $c$，执行以下操作：

• 初始时，令变量 $x := 0$。

• 对于 $i = 1, 2, \dots, N$，重复执行以下操作：

  • 若 $A_i = -1$，则将 $x$ 更新为 $x := \max(0, x - c)$。
  • 否则，将 $x$ 更新为 $x := x + A_i$。

回答 $Q$ 个如下形式的问题：

• 当参数 $c = C_i$ 时，求在整个操作序列中 $x$ 所能达到的最大值。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 3 \times 10^5$)。 第二行包含 $N$ 个整数 $A_i$ ($-1 \le A_i \le 10^6$)。 接下来的 $Q$ 行，每行包含一个整数 $C_i$，表示第 $i$ 个问题的参数值 ($0 \le C_i \le 10^6$)。

输出格式

输出 $Q$ 行。 在第 $i$ 行输出第 $i$ 个问题的答案。

样例

输入格式 1

20 11
50 100 50 100 0 200 -1 50 100 -1 200
-1 200 0 200 -1 200 200 -1 200
30
60
90
180
270
360
540
200
400
600
0

输出格式 1

1700
1550
1400
950
570
500
500
850
500
500
1850

说明

下面解释第一个样例输入中的第一个问题：

• 在该问题中，参数 $c = 30$。
• 初始时，$x = 0$。
• 由于 $A_1 = 50$，$x$ 更新为 $x = 0 + 50 = 50$。
• 由于 $A_2 = 100$，$x$ 更新为 $x = 50 + 100 = 150$。
• ...
• 由于 $A_6 = 200$，$x$ 更新为 $x = 300 + 200 = 500$。
• 由于 $A_7 = -1$，$x$ 更新为 $x = \max(0, 500 - 30) = 470$。
• ...
• 由于 $A_{19} = -1$，$x$ 更新为 $x = \max(0, 1530 - 30) = 1500$。
• 由于 $A_{20} = 200$，$x$ 更新为 $x = 1500 + 200 = 1700$。

包含省略的部分，在整个操作序列中 $x$ 所能达到的最大值为 $1700$。