Чтобы развлечь своих поклонников, гражданин НИТ решил дать им задачу, связанную с \(\operatorname{or} z\). А вы сможете её решить?
Дан массив \(a\) в 1-индексации, состоящий из \(n\) целых чисел, а также целое число \(z\). Вы можете проделать следующую операцию любое количество (возможно, ноль) раз:
- Выбрать целое \(i\), такое что \(1\le i\le n\). Затем одновременно присвоить \(a_i\) значение \((a_i\operatorname{or} z)\) и присвоить \(z\) значение \((a_i\operatorname{and} z)\). Другими словами, если \(x\) и \(y\) — текущие значения \(a_i\) и \(z\) соответственно, то нужно положить \(a_i\) равным \((x\operatorname{or}y)\), а \(z\) положить равным \((x\operatorname{and}y)\).
Здесь \(\operatorname{or}\) и \(\operatorname{and}\) обозначают операции побитового ИЛИ и побитового И соответственно.
Найдите максимально возможное значение максимального элемента в \(a\) после некоторого (возможно, нулевого) количества операций.
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу.
Примечание
В первом наборе входных данных одной из оптимальных последовательностей действий является следующая:
- Выполнить операцию для \(i=1\). Теперь \(a_1\) становится равным \((3\operatorname{or}3)=3\), а \(z\) становится равным \((3\operatorname{and}3)=3\).
- Выполнить операцию для \(i=2\). Теперь \(a_2\) становится равным \((4\operatorname{or}3)=7\), а \(z\) становится равным \((4\operatorname{and}3)=0\).
- Выполнить операцию для \(i=1\). Теперь \(a_1\) становится равным \((3\operatorname{or}0)=3\), а \(z\) становится равным \((3\operatorname{and}0)=0\).
После этих операций последовательность \(a\) становится равной \([3,7]\), и максимальное значение в ней равно \(7\). Можно доказать, что максимальное значение в \(a\) не может превосходить \(7\) ни при какой последовательности операций, так что ответ равен \(7\).
В четвёртом наборе входных данных одной из оптимальных последовательностей действий является следующая:
- Выполнить операцию для \(i=1\). Теперь \(a_1\) становится равным \((7\operatorname{or}7)=7\), а \(z\) становится равным \((7\operatorname{and}7)=7\).
- Выполнить операцию для \(i=3\). Теперь \(a_3\) становится равным \((30\operatorname{or}7)=31\), а \(z\) становится равным \((30\operatorname{and}7)=6\).
- Выполнить операцию для \(i=5\). Теперь \(a_5\) становится равным \((27\operatorname{or}6)=31\), а \(z\) становится равным \((27\operatorname{and}6)=2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3
3 4
5 5
0 2 4 6 8
1 9
10
5 7
7 15 30 29 27
3 39548743
10293834 10284344 13635445
|
7
13
11
31
48234367
|