Se te da una secuencia $A = (A_1, A_2, \dots, A_N)$ de longitud $N$ que consiste en enteros mayores o iguales a $-1$. Utilizando esta secuencia y un parámetro $c$, realiza las siguientes operaciones:

• Inicialmente, establece la variable $x := 0$.
• Para $i = 1, 2, \dots, N$, repite la siguiente operación:
  • Si $A_i = -1$, reemplaza $x$ con $x := \max(0, x - c)$.
  • De lo contrario, reemplaza $x$ con $x := x + A_i$.

Responde $Q$ preguntas de la siguiente forma:

• Cuando el parámetro $c = C_i$, encuentra el valor máximo alcanzado por $x$ a lo largo de toda la secuencia de operaciones.

Entrada

La primera línea contiene $N, Q$ en este orden. $(1 \le N, Q \le 3 \times 10^5)$

La segunda línea contiene $N$ enteros $A_i$. $(-1 \le A_i \le 10^6)$

Cada una de las siguientes $Q$ líneas contiene el valor de $C_i$ para la $i$-ésima pregunta. $(0 \le C_i \le 10^6)$

Salida

Imprime $Q$ líneas.

En la $i$-ésima de estas líneas, imprime la respuesta para la $i$-ésima pregunta.

Ejemplos

Entrada 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

Salida 1

1700
1550
1400
950
570
500
500
850
500
500
1850

Nota

Explicamos la primera pregunta de la primera entrada de ejemplo.

• En esta pregunta, el parámetro es $c = 30$.
• Inicialmente, la variable es $x = 0$.
• Como $A_1 = 50$, $x$ se actualiza a $x = 0 + 50 = 50$.
• Como $A_2 = 100$, $x$ se actualiza a $x = 50 + 100 = 150$.
• ...
• Como $A_6 = 200$, $x$ se actualiza a $x = 300 + 200 = 500$.
• Como $A_7 = -1$, $x$ se actualiza a $x = \max(0, 500 - 30) = 470$.
• ...
• Como $A_{19} = -1$, $x$ se actualiza a $x = \max(0, 1530 - 30) = 1500$.
• Como $A_{20} = 200$, $x$ se actualiza a $x = 1500 + 200 = 1700$.

Incluyendo las partes omitidas, el valor máximo alcanzado por $x$ a lo largo de toda la secuencia de operaciones es $1700$.