Xiao Zong is a child who loves eating Zongzi. Today, she is making Zongzi at home.

Xiao Zong has $n$ different types of Zongzi fillings in front of her, arranged in a row and numbered from $1$ to $n$ from left to right. The $i$-th type of filling has a non-negative integer attribute value $a_i$. There is an abundant supply of each type of filling, so Xiao Zong will not run out of ingredients. Xiao Zong plans to make $k$ Zongzi using these fillings.

Xiao Zong's method is as follows: choose two integers $l, r$ such that $1 \le l \le r \le n$, and mix all fillings with indices in the range $[l, r]$ to make one Zongzi. The deliciousness of the resulting Zongzi is the XOR sum of the attribute values of these fillings. (XOR is the common XOR operation, i.e., the ^ operator in C/C++ or the xor operator in Pascal.)

Xiao Zong wants to taste different flavors of Zongzi, so she does not want to make more than one Zongzi using the same set of fillings.

Xiao Zong wants to maximize the sum of the deliciousness of all the Zongzi she makes. Please help her find this value!

Input

The first line contains two positive integers $n$ and $k$, representing the number of fillings and the number of Zongzi Xiao Zong intends to make.

The next line contains $n$ non-negative integers, where the $i$-th number is $a_i$, representing the attribute value of the $i$-th filling.

For all input data, it is guaranteed that: $1 \le n \le 5 \times 10^5$, $1 \le k \le \min \left\{ \frac{n(n-1)}{2}, 2 \times 10^5 \right\}$, $0 \le a_i \le 4,294,967,295$.

Output

Output a single integer representing the maximum possible sum of the deliciousness of the Zongzi Xiao Zong can make.

Examples

Input 1

3 2
1 2 3

Output 1

6

Note 1

Xiao Zong can choose the two intervals $[3, 3]$ and $[1, 2]$ to make Zongzi. The deliciousness of both Zongzi is $3$, and the sum is $6$. It can be proven that no better solution exists.

Input 2

See xor/xor2.in and xor/xor2.ans in the contestant's directory.

Subtasks