D2. Максимум и запросы (сложная версия)
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между двумя версиями — это ограничения на $$$n$$$ и $$$q$$$, а также ограничения по времени и памяти. Вы можете делать взломы, только если обе версии задачи решены.

Теофанису очень нравится играть с битами чисел. У него есть массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$. Он может совершить не более $$$k$$$ операций с массивом, в каждой из которых он выбирает один элемент и увеличивает его на $$$1$$$.

Он нашел максимальное побитовое И, которое может иметь массив $$$a$$$ после выполнения не более чем $$$k$$$ операций.

Теофанис приложил много усилий, чтобы найти это значение, и был очень доволен своим результатом. К сожалению, Адас, будучи злым человеком, решил поиздеваться над ним, неоднократно меняя значение $$$k$$$.

Помогите Теофанису, вычислив максимально возможное побитовое И для $$$q$$$ различных значений $$$k$$$.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — длину массива и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — элементы массива.

Следующие $$$q$$$ строк описывают запросы. В $$$i$$$-й строке содержится одно целое число $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) — количество операций, которое может быть выполнено в $$$i$$$-м запросе.

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

Для каждого запроса выведите одно целое число — максимальное побитовое И, которое может иметь массив $$$a$$$ после выполнения не более чем $$$k_i$$$ операций.

Примеры
Входные данные
4 2
1 3 7 5
2
10
Выходные данные
2
6
Входные данные
3 5
4 0 2
9
8
17
1
3
Выходные данные
5
4
7
0
1
Входные данные
1 2
10
5
2318381298321
Выходные данные
15
2318381298331
Примечание

В первом наборе входных данных, в первом запросе, мы добавляем $$$1$$$ к первому и последнему элементу массива.

Таким образом, массив становится равен $$$[2,3,7,6]$$$ с побитовым И, равным $$$2$$$.

Во втором наборе входных данных, в первом запросе, мы добавляем $$$1$$$ к первому элементу, $$$5$$$ ко второму и $$$3$$$ к третьему, после чего все элементы становятся равны $$$5$$$.