异或和（xor）

题目描述

小 R 有一个长度为 n 的非负整数序列 a₁, a₂, …, aₙ。

定义一个区间 [l, r]（1 ≤ l ≤ r ≤ n）的权值为 aₗ, aₗ₊₁, …, aᵣ 的二进制按位异或和，即：

aₗ ⊕ aₗ₊₁ ⊕ … ⊕ aᵣ

其中，⊕ 表示二进制按位异或。

小 X 给了小 R 一个非负整数 k。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 k。

两个区间 [l₁, r₁]、[l₂, r₂] 相交，当且仅当两个区间同时包含至少一个相同的下标，即存在 1 ≤ i ≤ n，使得 l₁ ≤ i ≤ r₁ 且 l₂ ≤ i ≤ r₂。

例如，对于序列 [2, 1, 0, 3]：

• 若 k = 2，则小 R 可以选择区间 [1, 1] 和区间 [2, 4]，权值分别为 2 和 1 ⊕ 0 ⊕ 3 = 2。
• 若 k = 3，则小 R 可以选择区间 [1, 2] 和区间 [4, 4]，权值分别为 2 ⊕ 1 = 3 和 3。

你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

从文件 xor.in 中读入数据。

输入的第一行包含两个非负整数 n, k，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。

输入的第二行包含 n 个非负整数 a₁, a₂, …, aₙ，表示小 R 的序列。

输出格式

输出到文件 xor.out 中。

输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。

样例 1

输入

4 2
2 1 0 3

输出

2

解释

小 R 可以选择区间 [1, 1] 和区间 [2, 4]，异或和分别为 2 和 1 ⊕ 0 ⊕ 3 = 2。

可以证明，小 R 能选出的区间数量的最大值为 2。

样例 2

输入

4 3
2 1 0 3

输出

2

解释

小 R 可以选择区间 [1, 2] 和区间 [4, 4]，异或和分别为 2 ⊕ 1 = 3 和 3。

可以证明，小 R 能选出的区间数量的最大值为 2。

样例 3

输入

4 0
2 1 0 3

输出

1

解释

小 R 可以选择区间 [3, 3]，异或和为 0。

可以证明，小 R 能选出的区间数量的最大值为 1。

注意：小 R 不能同时选择区间 [3, 3] 和区间 [1, 4]，因为这两个区间同时包含下标 3。

样例 4

见选手目录下的 xor/xor4.in 与 xor/xor4.ans。

该样例满足测试点 4、5 的约束条件。

样例 5

见选手目录下的 xor/xor5.in 与 xor/xor5.ans。

该样例满足测试点 9、10 的约束条件。

样例 6

见选手目录下的 xor/xor6.in 与 xor/xor6.ans。

该样例满足测试点 14、15 的约束条件。

数据范围

对于所有测试数据，保证：

• 1 ≤ n ≤ 5 × 10⁵，0 ≤ k < 2²⁰；
• 对于所有 1 ≤ i ≤ n，均有 0 ≤ aᵢ < 2²⁰。

测试点编号	n ≤	k 的限制	特殊性质
1	2	k = 0	A
2	10	k ≤ 1	B
3	10²	k = 0	A
4、5		k ≤ 1	B
6～8		k ≤ 255	C
9、10	10³
11、12		k < 2²⁰	无
13	2 × 10⁵	k ≤ 1	B
14、15		k ≤ 255	C
16		k < 2²⁰	无
17	5 × 10⁵	k ≤ 255	C
18～20		k < 2²⁰	无

特殊性质 A： 对于所有 1 ≤ i ≤ n，均有 aᵢ = 1。

特殊性质 B： 对于所有 1 ≤ i ≤ n，均有 0 ≤ aᵢ ≤ 1。

特殊性质 C： 对于所有 1 ≤ i ≤ n，均有 0 ≤ aᵢ ≤ 255。