Andriana hatte ein wunderschönes zyklisches Array $a = (a_0, a_1, \dots, a_{n-1})$ aus $n$ ganzen Zahlen, wobei $0 \le a_i < 2^b$ für alle $0 \le i < n$ galt, aber leider hat sie es verloren! Für uns ist das jedoch ein großes Glück, denn ohne diese vergesslichen Protagonisten gäbe es auf der Welt viel weniger Rekonstruktionsprobleme.
Unterdessen hat Andrianas Freund Bob einige nützliche Informationen: Er führte ein Notizbuch, in dem er die bitweisen AND-Werte aufeinanderfolgender Teilabschnitte aus Andrianas Array notierte. Eines Tages war Bob ziemlich gelangweilt, also schrieb er für jede Position $i$ und eine feste Länge $k$ ($k \le n$) den Wert $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ auf (wobei die Indizes modulo $n$ genommen werden, da das Array zyklisch ist). Es ist nicht bekannt, ob Bob diese AND-Werte auf legalem Wege erworben hat.
Andriana möchte wissen, was der größte Wert von $k$ ist, sodass Bobs Notizbuch genügend Informationen enthält, um ihr geschätztes ursprüngliches Array eindeutig zu rekonstruieren.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ und $b$, wobei $n$ die Länge von Andrianas verlorenem Array ist und $b$ der Parameter ist, der die Bedingung $0 \le a_i < 2^b$ definiert. Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ — die Elemente des zyklischen Arrays.
Ausgabe
Gib eine einzige ganze Zahl aus — den größten Wert von $k$, sodass das Array $a$ eindeutig aus dem Array $x$ der Abschnitt-AND-Werte rekonstruiert werden kann.
Beschränkungen
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
Beispiele
Eingabe 1
6 3 7 3 7 7 3 7
Ausgabe 1
2
Hinweis
Im Beispiel gilt $n = 6, b = 3$. Das Array $a = [7, 3, 7, 7, 3, 7]$ hat die Binärdarstellung $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, wenn man drei Bits für jedes Element verwendet.
Für $k = 2$ wäre das Array $x$ gleich $[3, 3, 7, 3, 3, 7]$ (wobei $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Aus dem Array $x$ und dem Wert von $b$ können wir $a$ eindeutig rekonstruieren.
Für $k = 3$ wäre das Array $x$ gleich $[3, 3, 3, 3, 3, 3]$, was $a$ nicht eindeutig bestimmt (zum Beispiel würde $[3, 3, 7, 3, 7, 7]$ dasselbe $x$ liefern).
Daher lautet die Antwort für dieses Beispiel $k = 2$.