Дана последовательность $A = (A_1, A_2, \dots, A_N)$ длины $N$, состоящая из целых чисел, больших или равных $-1$. Используя эту последовательность и параметр $c$, выполните следующие операции:

• Изначально установите переменную $x := 0$.
• Для $i = 1, 2, \dots, N$ повторите следующую операцию:
  • Если $A_i = -1$, замените $x$ на $x := \max(0, x - c)$.
  • В противном случае замените $x$ на $x := x + A_i$.

Ответьте на $Q$ вопросов следующего вида:

• При заданном параметре $c = C_i$ найдите максимальное значение, которое принимает $x$ за всю последовательность операций.

Входные данные

Первая строка содержит $N$ и $Q$ в указанном порядке ($1 \le N, Q \le 3 \times 10^5$). Вторая строка содержит $N$ целых чисел $A_i$ ($-1 \le A_i \le 10^6$). Каждая из следующих $Q$ строк содержит значение $C_i$ для $i$-го вопроса ($0 \le C_i \le 10^6$).

Выходные данные

Выведите $Q$ строк. В $i$-й из этих строк выведите ответ на $i$-й вопрос.

Примеры

Входные данные 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

Выходные данные 1

1700
1550
1400
950
570
500
500
850
500
500
1850

Примечание

Разберем первый вопрос из первого примера.

• В этом вопросе параметр $c = 30$.
• Изначально переменная $x = 0$.
• Так как $A_1 = 50$, $x$ обновляется до $x = 0 + 50 = 50$.
• Так как $A_2 = 100$, $x$ обновляется до $x = 50 + 100 = 150$.
• ...
• Так как $A_6 = 200$, $x$ обновляется до $x = 300 + 200 = 500$.
• Так как $A_7 = -1$, $x$ обновляется до $x = \max(0, 500 - 30) = 470$.
• ...
• Так как $A_{19} = -1$, $x$ обновляется до $x = \max(0, 1530 - 30) = 1500$.
• Так как $A_{20} = 200$, $x$ обновляется до $x = 1500 + 200 = 1700$.

С учетом пропущенных частей, максимальное значение, достигнутое $x$ за всю последовательность операций, равно $1700$.