题目描述

Steven 有一个包含 $N$ 个非负整数的数组。数组中的第 $i$ 个整数（下标从 $0$ 开始）为 $A_i$。

Steven 非常喜欢 $A$ 的 异或偶 子区间。形式化地说，$A$ 的一个子区间是一对下标 $(L, R)$，表示元素 $A_L, A_{L+1}, \dots, A_{R-1}, A_R$。该子区间的异或和为 $A_L \text{ xor } A_{L+1} \text{ xor } \dots \text{ xor } A_{R-1} \text{ xor } A_R$，其中 xor 表示按位异或。

如果一个子区间的异或和的二进制表示中，值为 $1$ 的比特个数为偶数，则称该子区间是 异或偶 的。

Steven 希望对数组进行 $Q$ 次修改。第 $i$ 次修改将第 $P_i$ 个（下标从 $0$ 开始）元素更改为 $V_i$。Steven 想知道，在每次修改之后，$A$ 中元素个数最多的异或偶子区间的大小是多少？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$，分别表示 Steven 数组中的元素个数和修改次数。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示 Steven 数组中的第 $i$ 个元素 $A_i$。

随后 $Q$ 行，每行描述一次修改。第 $i$ 行包含 $P_i$ 和 $V_i$。第 $i$ 次修改将第 $P_i$ 个（下标从 $0$ 开始）元素更改为 $V_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y_1 y_2 ... y_Q，其中 $x$ 是测试用例编号（从 $1$ 开始），$y_i$ 是第 $i$ 次修改后 $A$ 中最大的异或偶子区间所包含的元素个数。如果不存在异或偶子区间，则输出 $0$。

2
4 3
10 21 3 7
1 13
0 32
2 22
5 1
14 1 15 20 26
4 26

Case #1: 4 3 4
Case #2: 4

提示

在样例 $1$ 中，$N = 4$，$Q = 3$。

• 第一次修改后，$A$ 为 $[10, 13, 3, 7]$。子区间 $(0, 3)$ 的异或和为 $10 \text{ xor } 13 \text{ xor } 3 \text{ xor } 7 = 3$。二进制下异或和为 $11_2$，其中 $1$ 的个数为 $2$（偶数），因此该子区间是异或偶的。这是最大的子区间，所以答案为 $4$。
• 第二次修改后，$A$ 为 $[32, 13, 3, 7]$。最大的异或偶子区间是 $(0, 2)$，其异或和为 $32 \text{ xor } 13 \text{ xor } 3 = 46$。二进制下为 $101110_2$。
• 第三次修改后，$A$ 为 $[32, 13, 22, 7]$。最大的异或偶子区间再次是 $(0, 3)$，其异或和为 $32 \text{ xor } 13 \text{ xor } 22 \text{ xor } 7 = 60$。二进制下为 $111100_2$。

在样例 $2$ 中，$N = 5$，$Q = 1$。第一次修改后，$A$ 为 $[14, 1, 15, 20, 26]$。最大的异或偶子区间是 $(1, 4)$，其异或和为 $1 \text{ xor } 15 \text{ xor } 20 \text{ xor } 26 = 0$。二进制下为 $0_2$。

限制条件

$1 \le T \le 100$。

$0 \le A_i < 1024$。

$0 \le P_i < N$。

$0 \le V_i < 1024$。

测试集 1（可见）

$1 \le N \le 100$。

$1 \le Q \le 100$。

测试集 2（隐藏）

$1 \le N \le 10^5$。

$1 \le Q \le 10^5$。

翻译由 DeepSeek V4 Pro 完成