Andriana átti fallegt hringfylki $a = (a_0, a_1, \dots, a_{n-1})$ með $n$ heiltölum, þar sem $0 \le a_i < 2^b$ fyrir öll $0 \le i < n$, en því miður týndi hún því! Hins vegar er þetta nokkuð mikil heppni fyrir okkur, því án þessara gleymnu aðalpersóna væru mun færri endurgerðarverkefni í heiminum.
Á meðan hefur Bob, vinur Andriönu, gagnlegar upplýsingar: hann hélt minnisbók þar sem hann skráði bitbundin AND-gildi samliggjandi búta úr fylki Andriönu. Dag einn leiddist Bob mjög, svo hann skrifaði niður, fyrir hverja stöðu $i$ og tiltekna fasta lengd $k$ ($k \le n$), gildið $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (þar sem vísar eru teknir módúló $n$, þar sem fylkið er hringfylki). Ekki er vitað hvort Bob aflaði þessara AND-gilda með löglegum hætti.
Andriana vill vita hvert stærsta gildið á $k$ er þannig að minnisbók Bobs innihaldi nægar upplýsingar til að endurgera dýrmæta upphaflega fylkið hennar á ótvíræðan hátt?
Inntak
Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ og $b$, þar sem $n$ er lengd týnda fylkisins hennar Andriönu og $b$ er stiki sem skilgreinir skorðuna $0 \le a_i < 2^b$. Önnur línan inniheldur $n$ heiltölur $a_i$ — stök hringfylkisins.
Úttak
Prentið eina heiltölu — stærsta gildið á $k$ þannig að hægt sé að endurgera fylkið $a$ á ótvíræðan hátt út frá fylkinu $x$ af AND-gildum búta.
Takmarkanir
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Dæmi
Inntak 1
6 3 7 3 7 7 3 7
Úttak 1
2
Athugasemd
Í dæminu er $n = 6, b = 3$. Fylkið $a = [7, 3, 7, 7, 3, 7]$ hefur tvíundarframsetninguna $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$ þegar notaðir eru þrír bitar fyrir hvert stak.
Fyrir $k = 2$ væri fylkið $x$ jafnt $[3, 3, 7, 3, 3, 7]$ (þar sem $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Út frá fylkinu $x$ og gildinu á $b$ getum við endurgert $a$ á ótvíræðan hátt.
Fyrir $k = 3$ væri fylkið $x$ jafnt $[3, 3, 3, 3, 3, 3]$, sem ákvarðar $a$ ekki á ótvíræðan hátt (til dæmis myndi $[3, 3, 7, 3, 7, 7]$ gefa sama $x$).
Þess vegna er svarið fyrir þetta dæmi $k = 2$.