Helloooo! Can you hear me?

Dany jest ciąg $A = (A_1, A_2, \dots, A_N)$ o długości $N$, składający się z liczb całkowitych większych lub równych $-1$. Używając tego ciągu oraz parametru $c$, wykonaj następujące operacje:

• Początkowo ustaw zmienną $x := 0$.
• Dla $i = 1, 2, \dots, N$ powtórz następującą operację:
  • Jeśli $A_i = -1$, zastąp $x$ przez $x := \max(0, x - c)$.
  • W przeciwnym razie zastąp $x$ przez $x := x + A_i$.

Odpowiedz na $Q$ pytań następującej postaci:

• Dla danego parametru $c = C_i$, znajdź maksymalną wartość osiągniętą przez $x$ w trakcie całego ciągu operacji.

Wejście

Pierwsza linia zawiera $N$ oraz $Q$ w tej kolejności. ($1 \le N, Q \le 3 \times 10^5$) Druga linia zawiera $N$ liczb całkowitych $A_i$. ($-1 \le A_i \le 10^6$) Każda z kolejnych $Q$ linii zawiera wartość $C_i$ dla $i$-tego pytania. ($0 \le C_i \le 10^6$)

Wyjście

Wypisz $Q$ linii. W $i$-tej z tych linii wypisz odpowiedź na $i$-te pytanie.

Przykład

Wejście 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

Wyjście 1

1700
1550
1400
950
570
500
500
850
500
500
1850

Uwagi

Wyjaśniamy pierwsze pytanie z pierwszego przykładu:

• W tym pytaniu parametr wynosi $c = 30$.
• Początkowo zmienna wynosi $x = 0$.
• Ponieważ $A_1 = 50$, $x$ jest aktualizowane do $x = 0 + 50 = 50$.
• Ponieważ $A_2 = 100$, $x$ jest aktualizowane do $x = 50 + 100 = 150$.
• ...
• Ponieważ $A_6 = 200$, $x$ jest aktualizowane do $x = 300 + 200 = 500$.
• Ponieważ $A_7 = -1$, $x$ jest aktualizowane do $x = \max(0, 500 - 30) = 470$.
• ...
• Ponieważ $A_{19} = -1$, $x$ jest aktualizowane do $x = \max(0, 1530 - 30) = 1500$.
• Ponieważ $A_{20} = 200$, $x$ jest aktualizowane do $x = 1500 + 200 = 1700$.

Wliczając pominięte części, maksymalna wartość osiągnięta przez $x$ w trakcie całego ciągu operacji wynosi $1700$.