Andriana possédait un magnifique tableau cyclique $a = (a_0, a_1, \dots, a_{n-1})$ de $n$ entiers, où $0 \le a_i < 2^b$ pour tout $0 \le i < n$, mais elle l'a malheureusement perdu ! Cependant, pour nous, c'est plutôt une chance, car sans ces protagonistes distraits, le monde compterait beaucoup moins de problèmes de reconstruction.
Pendant ce temps, Bob, l'ami d'Andriana, dispose d'informations utiles : il a conservé un carnet dans lequel il a noté les valeurs du ET bit à bit (AND) de segments consécutifs du tableau d'Andriana. Un jour où Bob s'ennuyait passablement, il a écrit, pour chaque position $i$ et une certaine longueur fixe $k$ ($k \le n$), la valeur $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (où les indices sont pris modulo $n$, puisque le tableau est cyclique). On ignore si Bob a obtenu ces valeurs AND par des moyens légaux.
Andriana aimerait savoir quelle est la plus grande valeur de $k$ telle que le carnet de Bob contienne suffisamment d'informations pour reconstruire de manière unique son précieux tableau d'origine.
Entrée
La première ligne de l'entrée contient deux entiers $n$ et $b$, où $n$ est la longueur du tableau perdu d'Andriana et $b$ est le paramètre définissant la contrainte $0 \le a_i < 2^b$. La deuxième ligne contient $n$ entiers $a_i$ — les éléments du tableau cyclique.
Sortie
Affichez un seul entier — la plus grande valeur de $k$ telle que le tableau $a$ puisse être reconstruit de manière unique à partir du tableau $x$ des AND de segments.
Contraintes
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Exemples
Entrée 1
6 3 7 3 7 7 3 7
Sortie 1
2
Remarque
Dans l'exemple, $n = 6, b = 3$. Le tableau $a = [7, 3, 7, 7, 3, 7]$ a pour représentation binaire $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, en utilisant trois bits pour chaque élément.
Pour $k = 2$, le tableau $x$ serait $[3, 3, 7, 3, 3, 7]$ (où $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). À partir du tableau $x$ et de la valeur de $b$, nous pouvons reconstruire $a$ de manière unique.
Pour $k = 3$, le tableau $x$ serait $[3, 3, 3, 3, 3, 3]$, ce qui ne détermine pas $a$ de manière unique (par exemple, $[3, 3, 7, 3, 7, 7]$ donnerait le même $x$).
Par conséquent, pour cet exemple, la réponse est $k = 2$.