D2. Красно-синие операции (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — максимальные значения $$$n$$$ и $$$q$$$.

Задан массив, состоящий из $$$n$$$ целых чисел. Изначально все элементы красные.

К массиву можно несколько раз применить следующую операцию. На $$$i$$$-й операции вы выбираете элемент массива; затем:

  • если элемент красный, то он увеличивается на $$$i$$$ и становится синим;
  • если элемент синий, то он уменьшается на $$$i$$$ и становится красным.

Операции нумеруются с $$$1$$$, т. е. на первой операции некоторый элемент изменяется на $$$1$$$ и так далее.

К массиву задаются $$$q$$$ запросов следующего вида:

  • дано целое число $$$k$$$, какой может быть наибольший минимум в массиве после того как вы примените ровно $$$k$$$ операций к нему?

Обратите внимание, что операции не изменяют массив между запросами, все запросы задаются к начальному массиву $$$a$$$.

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

В первой строке записано два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — количество элементов массива и количество запросов.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

В третьей строке записаны $$$q$$$ целых чисел $$$k_1, k_2, \dots, k_q$$$ ($$$1 \le k_j \le 10^9$$$).

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

На каждый запрос выведите одно целое число — наибольший минимум, который может быть в массиве после того как вы примените ровно $$$k$$$ операций к нему.

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