Migrated from Lutece 3113 猫饭

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：可持久化trie

小$w$最近在玩怪猎，他在怪猎中非常喜欢吃猫饭。

现在小$w$面前有 $n$ 种不同的猫饭，小$w$将它们从左往右摆成一排。第$i$ 种猫饭具有一个非负的属性值$a_i$。每种猫饭的制作材料数量都足够多，即每种猫饭的数量可以视作无限多。小$w$准备用这些猫饭来吃 $k$ 顿。

小$w$的做法是选两个整数$l$ 和 $r$，满足 $1\leq l \leq r \leq n$，将编号在$[l,r]$范围内的所有猫饭都吃掉，获得的满足度为这些猫饭属性的异或和。

小$w$喜欢新鲜感，所以不会选择同样的$[l,r]$两次或以上。

小$w$希望他能获得的满足感之和最大，现在帮他求出这个值吧。

Input

第一行两个正整数 $n , k$ ,表示猫饭的种数和小$w$吃饭的次数。

接下来一行为 $n$ 个非负整数，第 $i$ 个数为 $a_i$ ，表示第 $i$ 种猫饭的属性。

Output

输出一行一个整数，表示最大的满足感之和。

Samples

3 2
1 2 3

6

Constraints

$1\leq n \leq 5\times 10^5 , 1\leq k \leq \min( \frac{n(n-1}{2} , 2\times 10^5 ) , 0\leq a_i < 2^{30}$

Resources

2024 UESTC ICPC Training for Data Structure