M. Linked VERSE
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Helloooo! Can you hear me?

You are given a sequence $$$A=(A_1,A_2,\dots,A_N)$$$ of length $$$N$$$ consisting of integers greater than or equal to $$$-1$$$. Using this sequence and a parameter $$$c$$$, perform the following operations.

  • Initially, set the variable $$$x:=0$$$.
  • For $$$i=1,2,\dots,N$$$, repeat the following operation.
    • If $$$A_i = -1$$$, replace $$$x$$$ with $$$x := \max(0,x-c)$$$.
    • Otherwise, replace $$$x$$$ with $$$x := x+A_i$$$.

Answer $$$Q$$$ questions of the following form.

  • When the parameter $$$c=C_i$$$, find the maximum value attained by $$$x$$$ over the entire sequence of operations.
Input

The first line contains $$$N,Q$$$ in this order. $$$(1 \le N,Q \le 3 \times 10^5)$$$

The second line contains $$$N$$$ integers $$$A_i$$$. $$$(-1 \le A_i \le 10^6)$$$

Each of the following $$$Q$$$ lines contains the value of $$$C_i$$$ for the $$$i$$$-th question. $$$(0 \le C_i \le 10^6)$$$

Output

Print $$$Q$$$ lines.

On the $$$i$$$-th of these lines, print the answer to the $$$i$$$-th question.

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

We explain the first question of the first example input.

  • In this question, the parameter is $$$c=30$$$.
  • Initially, the variable is $$$x=0$$$.
  • Since $$$A_1 = 50$$$, $$$x$$$ is updated to $$$x=0+50=50$$$.
  • Since $$$A_2 = 100$$$, $$$x$$$ is updated to $$$x=50+100=150$$$.
  • $$$\dots$$$
  • Since $$$A_6=200$$$, $$$x$$$ is updated to $$$x=300+200=500$$$.
  • Since $$$A_7=-1$$$, $$$x$$$ is updated to $$$x = \max(0,500-30) = 470$$$.
  • $$$\dots$$$
  • Since $$$A_{19}=-1$$$, $$$x$$$ is updated to $$$x = \max(0,1530-30) = 1500$$$.
  • Since $$$A_{20}=200$$$, $$$x$$$ is updated to $$$x=1500+200=1700$$$.

Including the omitted parts, the maximum value attained by $$$x$$$ over the entire sequence of operations is $$$1700$$$.