5971 - NOIP CSP 2025 普及: 第三题异或和

通过次数

提交次数

旧版界面

Time Limit : 1 秒

Memory Limit : 512 MB

Input

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

输入的第二行包含 n 个非负整数 a1 ,a2 ,…,an ，表示小 R 的序列。

Output

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

Examples

Input

4 2
2 1 0 3

Output

Input

4 3
2 1 0 3

Output

Input

4 0
2 1 0 3

Output

Hint

说明/提示

【样例 1 解释】

小 R 可以选择区间 $[1, 1]$ 和区间 $[2, 4]$ ，异或和分别为 $2$ 和 $1 \oplus 0 \oplus 3 = 2$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 2 解释】

小 R 可以选择区间 $[1, 2]$ 和区间 $[4, 4]$ ，异或和分别为 $1 \oplus 2 = 3$ 和 $3$ 。可以证明，小 R 能选出的区间数量的最大值为 $2$ 。

【样例 3 解释】

小 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 \leq n \leq 5 \times 10^5$ , $0 \leq k < 2^{20}$ ;
对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i < 2^{20}$ 。

::cute-table{tuack}

测试点编号	$n \leq$	$k$	特殊性质
$1$	$2$	$=0$	A
$2$	$10$	$\leq 1$	B
$3$	$10^2$	$=0$	A
$4, 5$	^	$\leq 1$	B
$6 \sim 8$	^	$\leq 255$	C
$9, 10$	$10^3$	^	^
$11, 12$	^	$< 2^{20}$	无
$13$	$2 \times 10^5$	$\leq 1$	B
$14, 15$	^	$\leq 255$	C
$16$	^	$< 2^{20}$	无
$17$	$5 \times 10^5$	$\leq 255$	C
$18 \sim 20$	^	$< 2^{20}$	无

特殊性质 A: 对于所有 $1 \leq i \leq n$ ，均有 $a_i = 1$ 。

特殊性质 B: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 1$ 。

特殊性质 C: 对于所有 $1 \leq i \leq n$ ，均有 $0 \leq a_i \leq 255$ 。