Andrianalla oli kaunis $n$ kokonaisluvusta koostuva syklinen taulukko $a = (a_0, a_1, \dots, a_{n-1})$, missä $0 \le a_i < 2^b$ kaikilla $0 \le i < n$, mutta valitettavasti hän hukkasi sen! Meille tämä on kuitenkin melko onnekasta, sillä ilman tällaisia hajamielisiä päähenkilöitä maailmassa olisi paljon vähemmän rekonstruktiotehtäviä.
Sillä välin Andrianan ystävällä Bobilla on hyödyllistä tietoa: hän piti muistikirjaa, johon hän kirjasi Andrianan taulukon peräkkäisten osavälien bittikohtaisia AND-arvoja. Eräänä päivänä Bob oli melkoisen tylsistynyt, joten hän kirjoitti muistiin jokaiselle kohdalle $i$ ja jollekin kiinteälle pituudelle $k$ ($k \le n$) arvon $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (missä indeksit otetaan modulo $n$, koska taulukko on syklinen). Ei ole tiedossa, hankkiko Bob nämä AND-arvot laillisin keinoin.
Andriana haluaa tietää, mikä on suurin sellainen luvun $k$ arvo, että Bobin muistikirja sisältää tarpeeksi tietoa hänen rakkaan alkuperäisen taulukkonsa yksikäsitteiseen rekonstruoimiseen?
Syöte
Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $b$, missä $n$ on Andrianan kadonneen taulukon pituus ja $b$ on rajoituksen $0 \le a_i < 2^b$ määrittävä parametri. Toinen rivi sisältää $n$ kokonaislukua $a_i$ — syklisen taulukon alkiot.
Tuloste
Tulosta yksi kokonaisluku — suurin luvun $k$ arvo siten, että taulukko $a$ voidaan yksikäsitteisesti rekonstruoida osavälien AND-arvojen taulukosta $x$.
Rajoitukset
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Esimerkit
Syöte 1
6 3 7 3 7 7 3 7
Tuloste 1
2
Huomautus
Esimerkkitapauksessa $n = 6, b = 3$. Taulukon $a = [7, 3, 7, 7, 3, 7]$ binääriesitys on $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, kun jokaiselle alkiolle käytetään kolmea bittiä.
Kun $k = 2$, taulukko $x$ olisi $[3, 3, 7, 3, 3, 7]$ (missä $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Taulukosta $x$ ja luvun $b$ arvosta voimme rekonstruoida taulukon $a$ yksikäsitteisesti.
Kun $k = 3$, taulukko $x$ olisi $[3, 3, 3, 3, 3, 3]$, mikä ei määritä taulukkoa $a$ yksikäsitteisesti (esimerkiksi $[3, 3, 7, 3, 7, 7]$ tuottaisi saman taulukon $x$).
Näin ollen tässä esimerkissä vastaus on $k = 2$.