题目描述

Steven has an array of $N$ non-negative integers. The $i$-th integer (indexed starting from 0) in the array is $A_i$.

Steven really likes subintervals of $A$ that are xor-even. Formally, a subinterval of $A$ is a pair of indices $(L, R)$, denoting the elements $A_L, A_{L+1}, ..., A_{R-1}, A_R$. The xor-sum of this subinterval is $A_L \text{ xor } A_{L+1} \text{ xor } ... \text{ xor } A_{R-1} \text{ xor } A_R$, where xor is the bitwise exclusive or.

A subinterval is xor-even if its xor-sum has an even number of set bits in its binary representation.

Steven would like to make $Q$ modifications to the array. The $i$-th modification changes the $P_i$-th (indexed from 0) element to $V_i$. Steven would like to know, what is the size of the xor-even subinterval of A with the most elements after each modification?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case starts with a line containing two integers $N$ and $Q$, denoting the number of elements in Steven's array and the number of modifications, respectively.

The second line contains $N$ integers. The $i$-th of them gives $A_i$ indicating the $i$-th integer in Steven's array.

Then, $Q$ lines follow, describing the modifications. The $i$-th line contains $P_i$ and $V_i$. The $i$-th modification changes the $P_i$-th element to $V_i$, indicating that the $i$-th modification changes the $P_i$-th (indexed from 0) element to $V_i$.

输出格式

For each test case, output one line containing Case #x: y_1 y_2 . . . y_Q, where x is the test case number (starting from 1) and y_i is the number of elements in the largest xor-even subinterval of $A$ after the $i$-th modification. If there are no xor-even subintervals, then output 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

提示

In Sample Case 1, $N = 4$ and $Q = 3$.

• After the 1st modification, $A$ is $[10, 13, 3, 7]$. The subinterval $(0, 3)$ has xor-sum $10 \text{ xor } 13 \text{ xor } 3 \text{ xor } 7 = 3$. In binary, the xor-sum is $11_2$, which has an even number of $1$ bits, so the subinterval is xor-even. This is the largest subinterval possible, so the answer is $4$.
• After the 2nd modification, $A$ is $[32, 13, 3, 7]$. The largest xor-even subinterval is $(0, 2)$, which has xor-sum $32 \text{ xor } 13 \text{ xor } 3 = 46$. In binary, this is $101110_2$.
• After the 3rd modification, $A$ is $[32, 13, 22, 7]$. The largest xor-even subinterval is $(0, 3)$ again, which has xor-sum $32 \text{ xor } 13 \text{ xor } 22 \text{ xor } 7 = 60$. In binary, this is $111100_2$.

In Sample Case 2, $N = 5$ and $Q = 1$. After the 1st modification, $A$ is $[14, 1, 15, 20, 26]$. The largest xor-even subinterval is $(1, 4)$, which has xor sum $1 \text{ xor } 15 \text{ xor } 20 \text{ xor } 26 = 0$. In binary, this is $0_2$.

Limits

$1 \le T \le 100$.

$0 \le A_i < 1024$.

$0 \le P_i < N$.

$0 \le V_i < 1024$.

Test set 1 (Visible)

$1 \le N \le 100$.

$1 \le Q \le 100$.

Test set 2 (Hidden)

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

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