Пусть \(\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\) операций.
Выходные данные
Для каждого набора входных данных выведите единственную строку, содержащую максимально возможное \(\mathsf{AND}\) значение \(a_1\) \(\mathsf{AND}\) \(a_2\) \(\mathsf{AND}\) \(\dots\) \(\mathsf{AND}\) \(a_n\) после выполнения не более чем \(k\) операций.
Примечание
Для первого набора мы можем установить бит \(1\) (\(2^1\)) последних \(2\)-х элементов с помощью \(2\)-х операций, получив таким образом массив [\(2\), \(3\), \(3\)], значение \(\mathsf{AND}\) которого равно \(2\).
Для второго набора мы не можем выполнить никаких операций, поэтому ответом будет только \(\mathsf{AND}\) всего массива, равное \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|