题目描述

在未来世界，人类建造了一座巨大的 量子能量核心 来为城市供电。核心由 $n$ 个能量模块按顺序排列，每个模块都有一个能量编码 $a_i$。

为了稳定运行，工程师需要把这些模块划分为 $m$ 个 连续的能量区段。 在每个区段中，能量会发生 同步压缩反应：区段内所有模块的能量编码会进行一次 按位异或（XOR）运算，得到该区段的稳定能量值。 设第 $k$ 个区段的稳定能量为：

随后，所有区段的稳定能量会被送入 量子合成器。量子合成器会对这些能量进行 按位与（AND）融合，得到最终的核心输出能量：

为了让城市获得最大能量，你需要选择一种划分方式，使得最终输出能量 $E$ 最大。

说明：

• 异或：对于二进制下每一位，当且仅当两个值不同，异或输出为 $1$，否则为 $0$。
• 按位与：对于二进制下每一位，当且仅当两个值都为 $1$，按位与输出为 $1$，否则为 $0$。

输入格式

第一行输入两个正整数 $n$ 和 $m$，表示模块数量和区段数量。

第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个模块的能量编码。

输出格式

输出一个整数，表示最大输出能量。

样例 1 输入

4 2
7 7 3 7

样例 1 输出

3

样例 1 解释

将模块划分为 $2$ 个区段：

• 第 $1$ 个区段为 $[1, 1]$，总能量 $E_1 = a_1 = 7$；
• 第 $2$ 个区段为 $[2, 4]$，总能量 $E_2 = a_2 \oplus a_3 \oplus a_4 = 7 \oplus 3 \oplus 7 = 3$。

最终输出能量为：

可以证明该划分方案得到的输出能量是最大的。

样例 2

见选手目录下的 power/power2.in 和 power/power2.ans。 该测试用例满足测试点 $5 \sim 6$ 的约束条件。

样例 3

见选手目录下的 power/power3.in 和 power/power3.ans。 该测试用例满足测试点 $7 \sim 8$ 的约束条件。

样例 4

见选手目录下的 power/power4.in 和 power/power4.ans。 该测试用例满足测试点 $9 \sim 12$ 的约束条件。

数据范围

对于 $100\%$ 的数据，$2 \le n \le 3 \times 10^5$，$2 \le m \le n$，$0 \le a_i < 2^{31}$。

各测试点的附加限制如下表所示：

点击下载大样例