E. Maximum OR Popcount
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$n$$$ неотрицательных целых чисел.

Вы хотите решить $$$q$$$ независимых сценариев. В $$$i$$$-м сценарии вам разрешается выполнить следующую операцию не более чем $$$b_i$$$ раз:

  • Выбрать элемент массива и увеличить его на $$$1$$$.

Ваша цель — максимизировать количество битов, равных $$$1$$$, в побитовом ИЛИ всех чисел в массиве. Найдите это количество для каждого сценария.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 10^{5}$$$) — размер массива и количество сценариев.

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

$$$i$$$-я из следующих $$$q$$$ строк содержит одно целое число $$$b_i$$$ ($$$0 \leq b_i \leq 10^{9}$$$) — максимальное количество разрешенных операций в $$$i$$$-м сценарии.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^{5}$$$, и сумма $$$q$$$ по всем наборам входных данных не превышает $$$10^{5}$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк, $$$i$$$-я из которых содержит одно целое число — максимальное возможное количество битов побитового ИЛИ, равных $$$1$$$, в $$$i$$$-м сценарии.

Пример
Входные данные
3
1 3
0
0
2
4
2 2
1 3
0
3
2 1
1000000000 1000000000
1000000000
Выходные данные
0
1
2
2
3
31
Примечание

Ссылка на визуализатор

В первом наборе входных данных:

  • В первом сценарии у нас нет операций, и поэтому ответ равен количеству $$$1$$$-битов в побитовом ИЛИ исходного массива. Побитовое ИЛИ исходного массива равно $$$0$$$, и ответ тоже равен $$$0$$$.
  • Во втором сценарии один из способов достижения результата $$$1$$$ — это увеличить $$$a_1$$$ на $$$1$$$ дважды, получив побитовое ИЛИ равное $$$2={(10)}_2$$$. Можно показать, что это наилучшее значение, которое мы можем получить, выполнив операцию не более двух раз.
  • В третьем сценарии один из способов достижения результата $$$2$$$ — это добавить $$$1$$$ к $$$a_1$$$ трижды. Можно показать, что это оптимально. Обратите внимание, что вы не обязаны применять операцию $$$4$$$ раза.

Во втором наборе входных данных:

  • В первом сценарии у нас нет операций, и поэтому ответ равен количеству $$$1$$$-битов в побитовом ИЛИ исходного массива, $$$2$$$.
  • Во втором сценарии один из способов достижения результата $$$3$$$ — это добавить $$$1$$$ к $$$a_2$$$ трижды. Можно показать, что это оптимально.