Statement is not available in English language
H. Глеб и гринд
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Глеб любит играть в игру «Dewer Tofence». Изначально у Глеба есть набор из $$$n$$$ башен, высота башни $$$i$$$ равна $$$a_i$$$. Глеб перфекционист, поэтому высоты башен образуют строго возрастающую последовательность. Во время игры на каждом шаге $$$j$$$, начиная с $$$1$$$, происходит следующее:

Рассматриваются все башни с номерами $$$(2 \leq i \leq n)$$$, если разность высот башни $$$i$$$ и башни $$$i - 1$$$ равна $$$j$$$ (более формально $$$(a_i - a_{i - 1}) = j)$$$, то высота всех башен на отрезке $$$[i; n]$$$ увеличивается на $$$1$$$.

Цель игры — уничтожить монстров. Всего в игре есть $$$q$$$ различных монстров, монстр $$$i$$$ имеет $$$h_i$$$ единиц жизни. Так как Глеб перфекционист, он хочет убить каждого монстра ровно одним ударом. При ударе монстру наносится урон, равный сумме высот всех башен. Если это число больше или равно количеству единиц жизни монстра, то он умирает.

Для каждого из $$$q$$$ монстров Глеб хочет узнать, после какого шага игры он впервые сможет уничтожить этого монстра. При этом для каждого монстра игра начинается заново, то есть имеется $$$q$$$ независимых вопросов про монстров и для каждого нужно найти минимальный номер шага.

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

В первой строке содержится два целых числа $$$n$$$ $$$(2 \leq n \leq 10^6)$$$ и $$$q$$$ $$$(1 \leq q \leq 10^6)$$$.

Во второй строке записано $$$n$$$ целых чисел $$$a_i\; \; (1 \leq a_i \leq 10^9)$$$  — высота $$$i$$$-й башни.

Гарантируется, что $$$a_1, a_2, \dots, a_n$$$ строго возрастает.

В третьей строке записано $$$q$$$ целых чисел $$$h_i$$$ $$$(1 \leq h_i \leq 10^{18})$$$  — количество единиц жизни $$$i$$$-го монстра.

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

В единственной строке выведите $$$q$$$ чисел  — ответы на вопросы Глеба.

Система оценки
ГруппаБаллыДоп. ограниченияКомментарий
$$$0$$$$$$0$$$—Тесты из условия
$$$1$$$$$$24$$$$$$n,q \le 500$$$Каждый тест
$$$2$$$$$$24$$$$$$n,q \leq 8000$$$Каждый тест
$$$3$$$$$$14$$$$$$n,q \leq 10^5 $$$Каждый тест
$$$4$$$$$$21$$$$$$n,q \leq 5 \cdot 10^5$$$Каждый тест
$$$5$$$$$$17$$$—Каждый тест
Примеры
Входные данные
3 7
1 3 6
10 11 13 15 16 19 22
Выходные данные
0 2 3 3 4 5 6
Входные данные
2 2
1 2
400 1000000000000000000
Выходные данные
397 999999999999999997
Примечание

Рассмотрим первый тестовый пример:

Монстра с $$$10$$$ единицами жизни можно убить сразу же, ведь высота башен уже изначально $$$10$$$.

Монстра с $$$11$$$ единицами жизни можно убить только в момент времени $$$2$$$, так как при шаге $$$1$$$ ничего не произойдет с высотами башен, а на шаге $$$2$$$ высоты станут $$$[1, 4, 7]$$$.

На шаге $$$3$$$ высоты станут $$$[1, 5, 9]$$$.

Рассмотрим второй тестовой пример. На каждом шаге суммарная высота башен увеличивается на $$$1$$$ и высоты башен будут принимать вид $$$[1, 2 + j]$$$.