長さ $N$ の、$-1$ 以上の整数からなる数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。この数列とパラメータ $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$ $A_1$ $A_2$ $\dots$ $A_N$ $C_1$ $C_2$ $\vdots$ $C_Q$

制約: $1 \le N, Q \le 3 \times 10^5$ $-1 \le A_i \le 10^6$ * $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$ です。