У Андрианы был прекрасный циклический массив $a = (a_0, a_1, \dots, a_{n-1})$ из $n$ целых чисел, где $0 \le a_i < 2^b$ для всех $0 \le i < n$, но, к сожалению, она его потеряла! Впрочем, для нас это большая удача, ведь без таких забывчивых героев в мире было бы куда меньше задач на восстановление.
Тем временем у друга Андрианы Боба есть полезная информация: он вёл блокнот, в который записывал значения побитового И (AND) последовательных подотрезков массива Андрианы. Однажды Бобу было довольно скучно, поэтому он записал для каждой позиции $i$ и некоторой фиксированной длины $k$ ($k \le n$) значение $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (где индексы берутся по модулю $n$, так как массив циклический). Неизвестно, получил ли Боб эти значения AND законным путём.
Андриана хочет узнать, каково наибольшее значение $k$, при котором блокнот Боба содержал бы достаточно информации для однозначного восстановления её драгоценного исходного массива?
Входные данные
Первая строка входных данных содержит два целых числа $n$ и $b$, где $n$ — длина потерянного массива Андрианы, а $b$ — параметр, задающий ограничение $0 \le a_i < 2^b$. Вторая строка содержит $n$ целых чисел $a_i$ — элементы циклического массива.
Выходные данные
Выведите одно целое число — наибольшее значение $k$, при котором массив $a$ может быть однозначно восстановлен по массиву $x$ побитовых И подотрезков.
Ограничения
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Примеры
Входные данные 1
6 3 7 3 7 7 3 7
Выходные данные 1
2
Примечание
В примере $n = 6, b = 3$. Массив $a = [7, 3, 7, 7, 3, 7]$ имеет двоичное представление $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$ при использовании трёх битов для каждого элемента.
При $k = 2$ массив $x$ будет равен $[3, 3, 7, 3, 3, 7]$ (где $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). По массиву $x$ и значению $b$ мы можем однозначно восстановить $a$.
При $k = 3$ массив $x$ будет равен $[3, 3, 3, 3, 3, 3]$, что не определяет $a$ однозначно (например, $[3, 3, 7, 3, 7, 7]$ дал бы такой же массив $x$).
Следовательно, для этого примера ответом является $k = 2$.