Andriana aveva un bellissimo array ciclico $a = (a_0, a_1, \dots, a_{n-1})$ di $n$ interi, dove $0 \le a_i < 2^b$ per tutti gli $0 \le i < n$, ma sfortunatamente lo ha perso! Tuttavia, per noi, questa è una gran fortuna, poiché senza questi protagonisti smemorati il mondo avrebbe molti meno problemi di ricostruzione.
Nel frattempo, l'amico di Andriana, Bob, ha alcune informazioni utili: ha tenuto un taccuino in cui ha registrato i valori AND bit a bit di segmenti consecutivi dell'array di Andriana. Un giorno Bob era piuttosto annoiato, così ha annotato, per ogni posizione $i$ e una certa lunghezza fissa $k$ ($k \le n$), il valore $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (dove gli indici sono presi modulo $n$, poiché l'array è ciclico). Non è noto se Bob abbia acquisito questi valori AND con mezzi legali.
Andriana vuole sapere qual è il valore massimo di $k$ tale che il taccuino di Bob contenga informazioni sufficienti per ricostruire univocamente il suo prezioso array originale.
Input
La prima riga dell'input contiene due interi $n$ e $b$, dove $n$ è la lunghezza dell'array perduto di Andriana e $b$ è il parametro che definisce il vincolo $0 \le a_i < 2^b$. La seconda riga contiene $n$ interi $a_i$ — gli elementi dell'array ciclico.
Output
Stampa un singolo intero — il valore massimo di $k$ tale che l'array $a$ possa essere ricostruito univocamente dall'array $x$ degli AND dei segmenti.
Vincoli
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Esempi
Input 1
6 3 7 3 7 7 3 7
Output 1
2
Note
Nel caso d'esempio, $n = 6, b = 3$. L'array $a = [7, 3, 7, 7, 3, 7]$ ha rappresentazione binaria $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, usando tre bit per ciascun elemento.
Per $k = 2$, l'array $x$ sarebbe $[3, 3, 7, 3, 3, 7]$ (dove $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Dall'array $x$ e dal valore di $b$, possiamo ricostruire univocamente $a$.
Per $k = 3$, l'array $x$ sarebbe $[3, 3, 3, 3, 3, 3]$, che non determina univocamente $a$ (ad esempio, $[3, 3, 7, 3, 7, 7]$ darebbe lo stesso $x$).
Pertanto, per questo esempio, la risposta è $k = 2$.