AND Reconstruction

Обмеження: 2 сек., 512 МіБ

Andriana had a beautiful cyclic array \(a = (a_0, a_1, \dots, a_{n-1})\) of \(n\) integers, where \(0 \le a_i < 2^b\) for all \(0 \le i < n\), but unfortunately she lost it! However, for us, this is quite fortunate, as without these forgetful protagonists, the world would have many fewer reconstruction problems.

Meanwhile, Andriana’s friend Bob has some useful information: he kept a notebook where he recorded bitwise AND values of consecutive segments from Andriana’s array. Bob was quite bored one day, so he wrote down, for every position \(i\) and some fixed length \(k\) (\(k \le n\)), the value \[x_i = a_i \text{ AND } a_{i+1} \text{ AND } \ldots \text{ AND } a_{i+k-1},\] (where indices are taken modulo \(n\), since the array is cyclic). It is unknown whether Bob acquired these ANDs through legal means.

Andriana wants to know what the largest value of \(k\) is such that Bob’s notebook would contain enough information to uniquely reconstruct her treasured original array?

Вхідні дані

The first line of the input contains two integers \(n\) and \(b\), where \(n\) is the length of Andriana’s lost array and \(b\) is the parameter defining the constraint \(0 \le a_i < 2^b\).

The second line contains \(n\) integers \(a_i\) – the elements of the cyclic array.

Вихідні дані

Print a single integer – the largest value of \(k\) such that the array \(a\) can be uniquely reconstructed from the array \(x\) of segment ANDs.

Обмеження

\(3 \le n \le 2\cdot 10^5\),

\(1 \le b \le 30\),

\(0 \le a_i < 2^{b}\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 3 7 3 7 7 3 7	2

Примітки

In the sample case, \(n = 6, b = 3\). The array \(a = [7, 3, 7, 7, 3, 7]\) has binary representation \[[111_2, 011_2, 111_2, 111_2, 011_2, 111_2],\] using three bits for each element.

For \(k = 2\), the array \(x\) would be \([3, 3, 7, 3, 3, 7]\) (where \(x_i = a_i \text{ AND } a_{(i+1) \bmod 6}\)). From the array \(x\) and the value of \(b\), we can uniquely reconstruct \(a\).

For \(k = 3\), the array \(x\) would be \([3, 3, 3, 3, 3, 3]\), which does not uniquely determine \(a\) (for example, \([3, 3, 7, 3, 7, 7]\) would give the same \(x\)).

Therefore, for this sample, the answer is \(k = 2\).