H. Максимальный AND
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$\mathsf{AND}$$$ обозначает побитовую операцию И, а $$$\mathsf{OR}$$$ обозначает побитовую операцию ИЛИ.

Вам дан массив $$$a$$$ длины $$$n$$$ и неотрицательное целое число $$$k$$$. Вы можете выполнить не более чем $$$k$$$ операций над массивом следующего типа:

  • Выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и заменить $$$a_i$$$ на $$$a_i$$$ $$$\mathsf{OR}$$$ $$$2^j$$$, где $$$j$$$ - любое целое число от $$$0$$$ до $$$30$$$ включительно. Другими словами, в операции можно выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и установить $$$j$$$-й бит $$$a_i$$$ в $$$1$$$ ($$$0 \leq j \leq 30$$$).

Выведите максимально возможное значение $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ после выполнения не более чем $$$k$$$ операций.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Далее следует описание наборов.

Первая строка каждого набора содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$).

Затем следует единственная строка, содержащая $$$n$$$ целых чисел, описывающих массив $$$a$$$ ($$$0 \leq a_i < 2^{31}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите единственную строку, содержащую максимально возможное $$$\mathsf{AND}$$$ значение $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ после выполнения не более чем $$$k$$$ операций.

Пример
Входные данные
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1
Выходные данные
2
4
2147483646
1073741825
Примечание

Для первого набора мы можем установить бит $$$1$$$ ($$$2^1$$$) последних $$$2$$$-х элементов с помощью $$$2$$$-х операций, получив таким образом массив [$$$2$$$, $$$3$$$, $$$3$$$], значение $$$\mathsf{AND}$$$ которого равно $$$2$$$.

Для второго набора мы не можем выполнить никаких операций, поэтому ответом будет только $$$\mathsf{AND}$$$ всего массива, равное $$$4$$$.