Опис
Helloooo! Can you hear me?
Задано послідовність $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$.