Andriana 原本有一個美麗的循環陣列 $a = (a_0, a_1, \dots, a_{n-1})$,包含 $n$ 個整數,且對於所有 $0 \le i < n$ 均滿足 $0 \le a_i < 2^b$,但不幸的是她弄丟了它!不過對我們來說,這相當幸運,因為如果沒有這些健忘的主角,世界上就會少很多重構問題。
同時,Andriana 的朋友 Bob 有一些有用的資訊:他有一本筆記本,記錄了 Andriana 陣列中連續區間的按位元與(AND)值。有一天 Bob 非常無聊,因此他針對每個位置 $i$ 與某個固定長度 $k$($k \le n$)寫下了以下數值: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (因為陣列是循環的,所以索引對 $n$ 取模)。目前不清楚 Bob 是否透過合法途徑取得這些 AND 值。
Andriana 想知道,使得 Bob 的筆記本包含足夠資訊來唯一重構出她珍貴的原始陣列的最大 $k$ 值是多少?
輸入格式
輸入的第一行包含兩個整數 $n$ 和 $b$,其中 $n$ 是 Andriana 遺失的陣列長度,$b$ 是定義限制條件 $0 \le a_i < 2^b$ 的參數。 第二行包含 $n$ 個整數 $a_i$ —— 循環陣列的元素。
輸出格式
輸出一個整數 —— 能從區間 AND 陣列 $x$ 唯一重構出陣列 $a$ 的最大 $k$ 值。
資料範圍
$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.
範例
輸入格式 1
6 3 7 3 7 7 3 7
輸出格式 1
2
說明
在範例中,$n = 6, b = 3$。陣列 $a = [7, 3, 7, 7, 3, 7]$ 的二進位表示為 $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$,每個元素使用三個位元。
當 $k = 2$ 時,陣列 $x$ 會是 $[3, 3, 7, 3, 3, 7]$(其中 $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$)。由陣列 $x$ 與 $b$ 的值,我們可以唯一重構出 $a$。
當 $k = 3$ 時,陣列 $x$ 會是 $[3, 3, 3, 3, 3, 3]$,這無法唯一確定 $a$(例如 $[3, 3, 7, 3, 7, 7]$ 也會得到相同的 $x$)。
因此,對於此範例,答案為 $k = 2$。