Maximizing Sum of XOR over Disjoint Intervals

You are given two integers \(n\) and \(k\) along with a sequence \(a_1,a_2,\dots,a_n\). Your task is to select \(k\) non-overlapping intervals \([l_i,r_i]\) where \(1\le l_i\le r_i\le n\) for \(1\le i\le k\) such that the following expression is maximized:

\[ \max_{[l_i,r_i]} \sum_{i=1}^k \bigoplus_{j=l_i}^{r_i} a_j \]

Here, \(\oplus\) denotes the bitwise XOR operation.

Note: The input data is randomly generated.

inputFormat

The first line contains two integers \(n\) and \(k\), separated by a space.

The second line contains \(n\) space-separated integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output a single integer representing the maximum sum of XOR values from the chosen \(k\) disjoint intervals.

sample

3 1
1 2 3

3