Это сложная версия задачи. Единственное различие между двумя версиями — это ограничения на \(n\) и \(q\), а также ограничения по времени и памяти. Вы можете делать взломы, только если обе версии задачи решены.
Теофанису очень нравится играть с битами чисел. У него есть массив \(a\) длины \(n\) и целое число \(k\). Он может совершить не более \(k\) операций с массивом, в каждой из которых он выбирает один элемент и увеличивает его на \(1\).
Он нашел максимальное побитовое И, которое может иметь массив \(a\) после выполнения не более чем \(k\) операций.
Теофанис приложил много усилий, чтобы найти это значение, и был очень доволен своим результатом. К сожалению, Адас, будучи злым человеком, решил поиздеваться над ним, неоднократно меняя значение \(k\).
Помогите Теофанису, вычислив максимально возможное побитовое И для \(q\) различных значений \(k\).
Выходные данные
Для каждого запроса выведите одно целое число — максимальное побитовое И, которое может иметь массив \(a\) после выполнения не более чем \(k_i\) операций.
Примечание
В первом наборе входных данных, в первом запросе, мы добавляем \(1\) к первому и последнему элементу массива.
Таким образом, массив становится равен \([2,3,7,6]\) с побитовым И, равным \(2\).
Во втором наборе входных данных, в первом запросе, мы добавляем \(1\) к первому элементу, \(5\) ко второму и \(3\) к третьему, после чего все элементы становятся равны \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3 7 5
2
10
|
2
6
|
|
2
|
3 5
4 0 2
9
8
17
1
3
|
5
4
7
0
1
|
|
3
|
1 2
10
5
2318381298321
|
15
2318381298331
|