Hobanwoo has finally arrived at the Demon King's castle, but the door is locked and he cannot enter.

To open the door, he must transform a magic key of length $N$ into a magic key of length exactly $M$, while maximizing the power of the magic key.

A magic key of length $N$ consists of a sequence of $N$ non-negative integers $a_{1}, a_{2}, a_{3}, \dots, a_{N}$, and the power of the magic key is defined as the sum of the $N$ numbers in the sequence.

When the current length of the magic key is $ℓ$, you can reduce its length by applying one of the following 4 types of magic:

• Remove $a_{1}, a_{2}$ from the magic key and add $a_{1} \oplus a_{2}$ to the front to create a new magic key of length $ℓ-1$.
• Remove $a_{ℓ-1}, a_{ℓ}$ from the magic key and add $a_{ℓ-1} \oplus a_{ℓ}$ to the back to create a new magic key of length $ℓ-1$.
• Remove $a_{1}, a_{2}, a_{3}, a_{4}$ from the magic key and add $a_{2} \oplus a_{3}, a_{1} \oplus a_{4}$ to the front to create a new magic key of length $ℓ-2$.
• Remove $a_{ℓ-3}, a_{ℓ-2}, a_{ℓ-1}, a_{ℓ}$ from the magic key and add $a_{ℓ-3} \oplus a_{ℓ}, a_{ℓ-2} \oplus a_{ℓ-1}$ to the back to create a new magic key of length $ℓ-2$.

The changes for each operation are represented as follows:

$({\color{Red}a_{{\color{Red}1}}},\,\,{\color{Red}a_{{\color{Red}2}}},\,\,a_{3},\,\,a_{4}\,,\cdots,\,a_{ℓ}) \Rightarrow ({\color{Red}a_{{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}2}}},\,\,a_{3},\,\,a_{4}\,,\cdots,\,a_{ℓ})$ $(a_{1}\,,\cdots,\,a_{ℓ-3},\,\,a_{ℓ-2},\,\,{\color{Red}a_{{\color{Red}ℓ{\color{Red}-}{\color{Red}1}}}},\,\,{\color{Red}a_{{\color{Red}ℓ}}}) \Rightarrow (a_{1}\,,\cdots,\,a_{ℓ-3},\,\,a_{ℓ-2},\,\,{\color{Red}a_{{\color{Red}ℓ}{\color{Red}-}{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}ℓ}}})$ $({\color{Red}a_{{\color{Red}1}}},\,\,{\color{Blue}a_{{\color{Blue}2}}},\,\,{\color{Blue}a_{{\color{Blue}3}}},\,\,{\color{Red}a_{{\color{Red}4}}},\,\,a_{5},\,\,a_{6}\,,\cdots,\,a_{ℓ}) \Rightarrow ({\color{Blue}a_{{\color{Blue}2}}}{\color{Blue}⊕}{\color{Blue}a_{{\color{Blue}3}}},\,\,{\color{Red}a_{{\color{Red}1}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}4}}},\,\,a_{5},\,\,a_{6}\,,\cdots,\,a_{ℓ})$ $(a_{1}\,,\cdots,\,a_{ℓ-5},\,\,a_{ℓ-4},\,\,{\color{Red}a_{{\color{Red}ℓ}{\color{Red}-}{\color{Red}3}}},\,\,{\color{Blue}a_{{\color{Blue}ℓ}{\color{Blue}-}{\color{Blue}2}}},\,\,{\color{Blue}a_{{\color{Blue}ℓ}{\color{Blue}-}{\color{Blue}1}}},\,\,{\color{Red}a_{{\color{Red}ℓ}}}) \Rightarrow (a_{1}\,,\cdots,\,a_{ℓ-5},\,\,a_{ℓ-4},\,\,{\color{Red}a_{{\color{Red}ℓ}{\color{Red}-}{\color{Red}3}}}{\color{Red}⊕}{\color{Red}a_{{\color{Red}ℓ}}},\,\,{\color{Blue}a_{{\color{Blue}ℓ}{\color{Blue}-}{\color{Blue}2}}}{\color{Blue}⊕}{\color{Blue}a_{{\color{Blue}ℓ}{\color{Blue}-}{\color{Blue}1}}})$

Let's help Hobanwoo open the Demon King's castle door!

Input

The first line contains the length of the magic key $N$ and the target length $M$, separated by a space. $(4 \le M \le N \le 5\,000)$

The second line contains $N$ integers $a_{1}, a_{2}, a_{3}, \dots, a_{N}$, separated by spaces. $(0 \le a_{i} \le 10^{9})$

Output

Output the maximum possible power of the magic key when a magic key of length $M$ is created.

Note

$\oplus$ is the Bitwise XOR operation, which is performed bit by bit.

Bitwise XOR For each bit of the two numbers, the following operation is performed: If the two bits are different, the result is $1$; otherwise, it is $0$.

Example $$\begin{aligned} 0110_{2} &= 6 \\ \text{⊕} \ \ 1100_{2} &= 12 \\ \text{────} \\ 1010_{2} &= 10 \end{aligned}$$