X 아니면 무엇?

Steven은 N개의 음이 아닌 정수로 이루어진 배열을 가지고 있다. 배열의 i번째 정수(인덱스는 0부터 시작)는 $A_{i}$이다.

Steven은 A의 구간 중 xor-짝수인 것을 매우 좋아한다. 형식적으로, A의 구간은 인덱스의 쌍 (L, R)이며, 원소 $A_{L}$, $A_{L+1}$, ..., $A_{R-1}$, $A_{R}$을 나타낸다. 이 구간의 xor-합은 $A_{L}$ xor $A_{L+1}$ xor ... xor $A_{R-1}$ xor $A_{R}$이며, 여기서 xor는 비트 단위 배타적 논리합이다.

구간의 xor-합을 이진 표현으로 나타냈을 때 설정된 비트의 수가 짝수이면 그 구간은 xor-짝수이다.

Steven은 배열을 Q번 수정하려 한다. i번째 수정은 $P_{i}$번째(인덱스는 0부터 시작) 원소를 $V_{i}$로 변경한다. Steven은 각 수정 후 A의 xor-짝수 구간 중 원소가 가장 많은 구간의 크기를 알고 싶어 한다.

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 0 ≤ $A_{i}$ < 1024. 0 ≤ $P_{i}$ < N. 0 ≤ $V_{i}$ < 1024.

테스트 세트 1 (공개)

1 ≤ N ≤ 100. 1 ≤ Q ≤ 100.

테스트 세트 2 (비공개)

1 ≤ N ≤ $10^{5}$. 1 ≤ Q ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 정수 N과 Q가 포함된 한 줄로 시작하며, 이들은 각각 Steven의 배열에 있는 원소의 수와 수정 횟수를 나타낸다.

두 번째 줄에는 N개의 정수가 주어진다. 그중 i번째 정수로 $A_{i}$가 주어지며, 이는 Steven의 배열에 있는 i번째 정수를 나타낸다.

그다음 수정 내용을 설명하는 Q개의 줄이 주어진다. i번째 줄에는 $P_{i}$와 $V_{i}$가 주어진다. 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의 가장 큰 xor-짝수 구간에 포함된 원소의 수이다. xor-짝수 구간이 하나도 없다면 0을 출력한다.

예제 케이스 1에서 N = 4이고 Q = 3이다.

• 1st 수정 후 A는 $[10, 13, 3, 7]$이다. 구간 (0, 3)의 xor-합은 10 xor 13 xor 3 xor 7 = 3이다. 이진 표현에서 xor-합은 11_{2}이며, 1 비트의 수가 짝수이므로 이 구간은 xor-짝수이다. 이는 가능한 가장 큰 구간이므로 답은 4이다.

• 2nd 수정 후 A는 $[32, 13, 3, 7]$이다. 가장 큰 xor-짝수 구간은 (0, 2)이며, xor-합은 32 xor 13 xor 3 = 46이다. 이진 표현으로는 101110_{2}이다.

• 3rd 수정 후 A는 $[32, 13, 22, 7]$이다. 가장 큰 xor-짝수 구간은 다시 (0, 3)이며, xor-합은 32 xor 13 xor 22 xor 7 = 60이다. 이진 표현으로는 111100_{2}이다.

예제 케이스 2에서 N = 5이고 Q = 1이다. 1st 수정 후 A는 $[14, 1, 15, 20, 26]$이다. 가장 큰 xor-짝수 구간은 (1, 4)이며, xor 합은 1 xor 15 xor 20 xor 26 = 0이다. 이진 표현으로는 0_{2}이다.