Andriana hadde en vakker syklisk tabell $a = (a_0, a_1, \dots, a_{n-1})$ med $n$ heltall, der $0 \le a_i < 2^b$ for alle $0 \le i < n$, men dessverre mistet hun den! For oss er dette imidlertid ganske heldig, for uten disse glemsomme hovedpersonene ville verden hatt langt færre rekonstruksjonsoppgaver.
I mellomtiden har Andrianas venn Bob noen nyttige opplysninger: han hadde en notatbok der han noterte bitvise AND-verdier av påfølgende segmenter fra Andrianas tabell. En dag kjedet Bob seg ganske mye, så han skrev ned, for hver posisjon $i$ og en fast lengde $k$ ($k \le n$), verdien $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (der indeksene tas modulo $n$, siden tabellen er syklisk). Det er ukjent om Bob skaffet seg disse AND-verdiene på lovlig vis.
Andriana vil vite hva den største verdien av $k$ er slik at Bobs notatbok vil inneholde nok informasjon til å entydig rekonstruere hennes kjære opprinnelige tabell?
Inndata
Den første linjen i inndataene inneholder to heltall $n$ og $b$, der $n$ er lengden på Andrianas tapte tabell og $b$ er parameteren som definerer begrensningen $0 \le a_i < 2^b$. Den andre linjen inneholder $n$ heltall $a_i$ — elementene i den sykliske tabellen.
Utdata
Skriv ut et enkelt heltall — den største verdien av $k$ slik at tabellen $a$ kan rekonstrueres entydig fra tabellen $x$ med segment-AND-verdier.
Begrensninger
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Eksempler
Inndata 1
6 3 7 3 7 7 3 7
Utdata 1
2
Merk
I eksempelet er $n = 6, b = 3$. Tabellen $a = [7, 3, 7, 7, 3, 7]$ har binærrepresentasjonen $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, med tre biter for hvert element.
For $k = 2$ ville tabellen $x$ vært $[3, 3, 7, 3, 3, 7]$ (der $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Fra tabellen $x$ og verdien av $b$ kan vi entydig rekonstruere $a$.
For $k = 3$ ville tabellen $x$ vært $[3, 3, 3, 3, 3, 3]$, noe som ikke entydig bestemmer $a$ (for eksempel ville $[3, 3, 7, 3, 7, 7]$ gitt samme $x$).
Derfor er svaret for dette eksempelet $k = 2$.