У Андріани був чудовий циклічний масив $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$.