课间休息时,Vanya 来到班级,看到黑板上有一个由 $$$n$$$ $$$k$$$ 位整数 $$$a_1、a_2、\ldots、a_n$$$ 组成的数组。如果 $$$0 \leq x $$$ 被称为 $$$k$$$ 位整数,如果 $$$0 \leq x \leq 2^k - 1$$$。
当然,Vanya无法抗拒,开始改变黑板上写的数字。为了确保没有人注意到任何事情,Vanya 只允许自己进行一种类型的更改:选择数组 $$$i$$$ 的索引 ($$$1 \leq i \leq n$$$) 并将数字 $$$a_i$$$ 替换为数字 $$$\overline{a_i}$$$。我们将 $$$k$$$ 位整数 $$$x$$$ 定义为 $$$k$$$ 位整数,使得它的所有 $$$k$$$ 位与 $$$x$$$ 的相应位不同。
Vanya 不喜欢 $$$0$$$ 这个数字。因此,他喜欢这样的段$$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$),使得$$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0$$$,其中$$$\oplus$$$表示按位异或运算。确定他喜欢 Vanya 可以应用零个或多个上述操作获得的最大段数。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq k \leq 30$$$)。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2^k - 1$$$),用空格分隔 - $$$k$$$ 位整数的数组。
输出
打印一个整数——异或不等于 $$$0$$$ 的最大可能段数,可以通过执行语句中描述的多次(可能是 $$$0$$$)操作来获得。
示例
输入 #1
3 2 1 3 0
输出 #1
5
输入 #2
6 3 1 4 4 7 3 4
输出 #2
19
注意
在第一个示例中,如果 Vasya 不执行任何操作,他会得到一个包含 Vanya 喜欢的 $$$5$$$ 段的数组。如果他用 $$$i = 2$$$ 执行运算,他会得到一个数组 $$$[1, 0, 0]$$$,因为当 $$$k = 2$$$ 时,$$$\overline{3} = 0$$$。该数组有 Vanya 喜欢的 $$$3$$$ 段。另外,为了获得 Vanya 喜欢的具有 $$$5$$$ 段的数组,他可以执行 $$$i = 3$$$ 和 $$$i = 2$$$ 两个操作。然后他得到一个数组 $$$[1, 0, 3]$$$。可以证明他无法获得$$$6$$$或更多他喜欢的片段。
在第二个示例中,为了获得 Vanya 喜欢的 $$$19$$$ 片段,他可以使用 $$$i = 3$$$、$$$i = 4$$$、$$$i = 5$$$、$$$i = 6$$$ 执行 $$$4$$$ 操作,并得到一个数组 $$$[1, 4, 3, 0, 4, 3]$$$。