Волшебник ORZ любит колдовать над числами. Вы решили проверить его силу и дали ему массив a, состоящий из n целых чисел, а также целое число z. Нумерация элементов массива начинается с 1.
Волшебник ORZ проделывает следующую операцию любое количество (возможно, ноль) раз:
- Он выбирает целое число
i, такое что 1<= i <= n. Затем он шепчет заклинание и после этого одновременно число ai превращается в число равное (ai or z), а число z превращается в число, равное (ai and z).
Здесь or и and обозначают операции побитового ИЛИ и побитового И соответственно.
Найдите максимально возможное значение максимального элемента в массиве a после некоторого (возможно, нулевого) количества превращений.
Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 2
30). Вторая строка набора входных данных содержит n целых чисел:
a1,
a2,
...,
an (0 <=
ai < 2
30). Гарантируется, что сумма значений
n по всем наборам входных данных не превосходит 10
4.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
2 3
3 4 |
7 |
Одной из оптимальных последовательностей действий является следующая:
- Выполнить операцию для
i = 1. Теперь a1 становится равным (3 or 3) = 3, а z становится равным (3 and 3) = 3.
- Выполнить операцию для
i = 2. Теперь a2 становится равным (4 or 3) = 7,, а z становится равным (3 and 3) = 0.
- Выполнить операцию для
i = 1. Теперь a1 становится равным (3 or 0) = 3, а z становится равным (3 and 0) = 0.
После этих операций последовательность a становится равной [3,7], и максимальное значение в ней равно 7. Можно доказать, что максимальное значение в a не может превосходить 7 ни при какой последовательности операций, так что ответ равен 7.
|
| 2 |
5 5
0 2 4 6 8 |
13 |
|