Vous disposez d'une séquence $A = (A_1, A_2, \dots, A_N)$ de longueur $N$ composée d'entiers supérieurs ou égaux à $-1$. En utilisant cette séquence et un paramètre $c$, effectuez les opérations suivantes :

• Initialement, fixez la variable $x := 0$.
• Pour $i = 1, 2, \dots, N$, répétez l'opération suivante :
  • Si $A_i = -1$, remplacez $x$ par $x := \max(0, x - c)$.
  • Sinon, remplacez $x$ par $x := x + A_i$.

Répondez à $Q$ questions de la forme suivante :

• Lorsque le paramètre $c = C_i$, trouvez la valeur maximale atteinte par $x$ sur l'ensemble de la séquence d'opérations.

Entrée

La première ligne contient $N$ et $Q$ dans cet ordre. $(1 \le N, Q \le 3 \times 10^5)$

La deuxième ligne contient $N$ entiers $A_i$. $(-1 \le A_i \le 10^6)$

Chacune des $Q$ lignes suivantes contient la valeur de $C_i$ pour la $i$-ième question. $(0 \le C_i \le 10^6)$

Sortie

Imprimez $Q$ lignes.

Sur la $i$-ième de ces lignes, imprimez la réponse à la $i$-ième question.

Exemples

Entrée 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

Sortie 1

1700
1550
1400
950
570
500
500
850
500
500
1850

Remarque

Nous expliquons la première question de la première entrée d'exemple.

• Dans cette question, le paramètre est $c = 30$.
• Initialement, la variable est $x = 0$.
• Comme $A_1 = 50$, $x$ est mis à jour à $x = 0 + 50 = 50$.
• Comme $A_2 = 100$, $x$ est mis à jour à $x = 50 + 100 = 150$.
• ...
• Comme $A_6 = 200$, $x$ est mis à jour à $x = 300 + 200 = 500$.
• Comme $A_7 = -1$, $x$ est mis à jour à $x = \max(0, 500 - 30) = 470$.
• ...
• Comme $A_{19} = -1$, $x$ est mis à jour à $x = \max(0, 1530 - 30) = 1500$.
• Comme $A_{20} = 200$, $x$ est mis à jour à $x = 1500 + 200 = 1700$.

En incluant les parties omises, la valeur maximale atteinte par $x$ sur l'ensemble de la séquence d'opérations est $1700$.