C. Осада Вальгаллы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ивар Бескостный — великий лидер. Он пытается захватить Каттегат, в данный момент находящийся под контролем Лагерты. Битва началась, и волны воинов Ивара гибнут одна за другой.

У Ивара $$$n$$$ воинов, он выставляет их вдоль прямой напротив главных ворот так, что $$$i$$$-й воин стоит сразу за $$$(i-1)$$$-м воином. Первый воин возглавляет атаку.

Каждый атакующий воин может выдержать до $$$a_i$$$ стрел, прежде чем он падёт, где $$$a_i$$$ — сила $$$i$$$-го воина.

Лагерта приказывает своим воинам выпустить $$$k_i$$$ стрел в течение $$$i$$$-й минуты, стрелы одна за одной поражают первого всё ещё стоящего воина. После того, как все воины Ивара падут и стрелы, находящиеся в воздухе в данный момент, пролетят, Тор бьёт по земле своим молотом и все воины Ивара получают свои силы назад и возвращаются в битву. Другими словами, если все воины умрут в минуту $$$t$$$, в конце этой минуты $$$t$$$ они все встанут и будут сражаться.

Битва будет идти $$$q$$$ минут. После каждой минуты вы должны сообщить Ивару, сколько из его воинов находится в строю.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \leq 200\,000$$$) — число воинов Ивара и длительность боя в минутах.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), обозначающих силы воинов Ивара.

Третья строка содержит $$$q$$$ целых чисел $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq 10^{14}$$$), $$$i$$$-е из которых означает число стрел $$$k_i$$$, которое будет выпущено в воинов Ивара по приказу Лагерты в минуту $$$i$$$.

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

Выведите $$$q$$$ строк, $$$i$$$-я из которых содержит число воинов Ивара, находящихся в строю после $$$i$$$-й минуты.

Примеры
Входные данные
5 5
1 2 1 2 1
3 10 1 1 1
Выходные данные
3
5
4
4
3
Входные данные
4 4
1 2 3 4
9 1 10 6
Выходные данные
1
4
4
1
Примечание

В первом примере:

  • после 1-й минуты 1-й и 2-й воины умрут.
  • после 2-й минуты все воины умрут (а оставшиеся стрелы будут потрачены впустую), после чего их воскресят, поэтому ответ — 5, все воины живы.
  • после 3-й минуты 1-й воин умирает.
  • после 4-й минуты во 2-го воина попадут и его сила упадёт на 1.
  • после 5-й минуты 2-й воин умрёт.