Mocha — школьница старших классов. В школе она получила от учителей много знаний, особенно от учителя математики. Недавно Mocha узнала о двоичной системе счисления и заинтересовалась битовыми операциями.
Сегодня у Mocha есть массив целых чисел \(a\) длины \(n\). За одну операцию она может выбрать произвольный отрезок \([l, r]\) и для всех значений \(i\) (\(0\leq i \leq r-l\)) одновременно заменить \(a_{l+i}\) на \(a_{l+i} \,\&\, a_{r-i}\), где \(\&\) обозначает операцию побитового И. Эта операция может быть выполнена произвольное количество раз.
Например, если \(n=5\), исходный массив \([a_1,a_2,a_3,a_4,a_5]\), и Mocha выбирает отрезок \([2,5]\), то после применения операции массив будет равен \([a_1,a_2\,\&\, a_5, a_3\,\&\, a_4, a_4\,\&\, a_3, a_5\,\&\, a_2]\).
Mocha хочет сделать максимальное значение в массиве как можно меньше. Помогите, как лучший друг, вычислить это минимально возможное значение максимума?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможное значение максимума после применения некоторого количества операций.
Примечание
В первом наборе входных данных Mocha может выбрать отрезок \([1,2]\), и массив становится равным \([ 0, 0]\), так как первый элемент становится равен \(1\,\&\,2\), а второй — \(2\,\&\,1\).
Во втором наборе входных данных Mocha может выбрать отрезок \([1,3]\), и массив становится равным \([ 1,1,1]\), где первый элемент равен \(1\,\&\,3\), второй элемент — \(1\,\&\,1\), а третий элемент — \(3\,\&\,1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
3
1 1 3
4
3 11 3 7
5
11 7 15 3 7
|
0
1
3
3
|