Відновлення за AND

Обмеження: 2 сек., 512 МіБ

Андріана мала чудовий циклічний масив \(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 } \ldots \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\) значень AND для фрагментів.

Обмеження

\(3 \le n \le 2\cdot 10^5\),

\(1 \le b \le 30\),

\(0 \le a_i < 2^{b}\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 3 7 3 7 7 3 7	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\).