Description
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$, update $x$ to $x := \max(0, x - c)$.
- Otherwise, update $x$ to $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 two integers $N$ and $Q$ ($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 an integer $C_i$, representing the parameter value for the $i$-th question ($0 \le C_i \le 10^6$).
Output
Print $Q$ lines. On the $i$-th line, print the answer to the $i$-th question.
Examples
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
We explain the first question of the first example input:
- In this question, the parameter is $c = 30$.
- Initially, $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$.
- ...
- 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$.
- ...
- 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$.