AND Reconstruction#13009

AND Reconstruction

2 seconds
512 megabytes
Hard

Andriana had a beautiful cyclic array a = (a_0, a_1, \dots, a_{n-1}) of 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 and some fixed length (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 , 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 is such that Bob’s notebook would contain enough information to uniquely reconstruct her treasured original array?

Input

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

The second line contains integers a_i – the elements of the cyclic array.

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

1 \le b \le 30,

0 \le a_i < 2^{b}.

Output

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

Examples

Example

Loading
Loading

Note

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 would be [3, 3, 7, 3, 3, 7] (where x_i = a_i \text{ AND } a_{(i+1) \bmod 6}). From the array and the value of , we can uniquely reconstruct .

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

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