Andriana は $n$ 個の整数からなる美しい巡回配列 $a = (a_0, a_1, \dots, a_{n-1})$(すべての $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$ の値がいくらであるかを知りたいと思っています。
入力
入力の最初の行には2つの整数 $n$ と $b$ が含まれます。ここで、$n$ は Andriana が失くした配列の長さであり、$b$ は制約 $0 \le a_i < 2^b$ を定めるパラメータです。 2行目には、巡回配列の要素を表す $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]$ は、各要素に3ビットを用いると二進表記で $[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$ です。