KUPC 2025 2026/03/28 09:00 ~ 2026/03/28 14:00 5:00:00.000

M Linked VERSE

問題
制限時間: 7 sec メモリ制限: 1024 MB
Linked VERSE
Statement

……ｻﾞｻﾞｰｯ…··もし…もー…… ····ｻﾞｯ……き…えま…か？… ······ｻﾞｻﾞｯ……

\(-1\) 以上の整数からなる長さ \(N\) の数列 \(A=(A_1,A_2,\dots,A_N)\) が与えられます。この数列とパラメータ \(c\) を用いて以下の操作を行います。

  • 最初、変数 \(x:=0\) とする。
  • \(i=1,2,\dots,N\) について以下の操作を繰り返す。
    • \(A_i = -1\) であるとき、 \(x := \max(0,x-c)\) と置き換える。
    • そうでないとき、 \(x := x+A_i\) と置き換える。

以下の形式の質問に \(Q\) 個答えてください。

  • パラメータ \(c=C_i\) としたとき、操作全体にわたって \(x\) がとる最大値を求めよ。

Input

\(1\) 行目に \(N,Q\) がこの順に与えられる。 \((1 \le N,Q \le 3 \times 10^5)\)

\(2\) 行目に \(N\) 個の整数 \(A_i\) が与えられる。 \((-1 \le A_i \le 10^6)\)

続く \(Q\) 行のうち \(i\) 行目に、 \(i\) 個目の質問における \(C_i\) の値が与えられる。 \((0 \le C_i \le 10^6)\)

Output

\(Q\) 行出力せよ。

そのうち \(i\) 行目には、 \(i\) 個目の質問に対する答えを出力せよ。

Example

Input 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
Output 1
1700
1550
1400
950
570
500
500
850
500
500
1850

Note

\(1\) 個目のサンプル入力の \(1\) 個目の質問について説明します。

  • この質問では、パラメータ \(c=30\) とする。
  • 最初、変数 \(x=0\) である。
  • \(A_1 = 50\) である。 \(x=0+50=50\) と更新される。
  • \(A_2 = 100\) である。 \(x=50+100=150\) と更新される。
  • \(\dots\)
  • \(A_6=200\) である。 \(x=300+200=500\) と更新される。
  • \(A_7=-1\) である。 \(x = \max(0,500-30) = 470\) と更新される。
  • \(\dots\)
  • \(A_{19}=-1\) である。 \(x = \max(0,1530-30) = 1500\) と更新される。
  • \(A_{20}=200\) である。 \(x=1500+200=1700\) と更新される。

省略された部分も含め、操作全体にわたって \(x\) がとる最大値は \(1700\) です。

サンプル