XOr

Time limit1sMemory limit1024 MB

Summary

Split an array into exactly m consecutive parts so the OR of the parts' XOR sums is as small as possible, and print that minimum.

Level: Hard8 of 10
Topics: Bit manipulation, Greedy, Prefix sum, Dynamic programming
Solved: No attempts yet

Problem

bobo has a sequence of integers $a\_1, a\_2, \dots, a\_n$ . He divides the sequence into exactly $m$ consecutive parts.

The cost of each part is its xor sum (bitwise exclusive-or). The cost of the division is the bitwise or sum of the costs of its parts.

Help bobo find the minimum cost.

Input

The first line contains two integers $n$ , $m$ ( $1 \leq n \leq 200000, 1 \leq m \leq n$ ). The second line contains $n$ integers $a\_1, a\_2, \dots, a\_n$ ( $0 \leq a\_i \leq 10^9$ ).

Output

Print the minimum cost as a single integer.

Examples2

Example 1
Input
```
3 2
1 3 2
```
Expected output
```
1
```
Example 2
Input
```
4 3
1 2 0 2
```
Expected output
```
3
```