Given a sequence of nn numbers a1 ,a2,⋯,an and three functions.
Define a function f(l,r)f(l,r) which returns \oplus a[x]⊕a[x] (l \le x \le rl≤x≤r). The \oplus⊕ represents exclusive OR.
Define a function g(l,r)g(l,r) which returns \oplus f(x,y)(l \le x \le y \le r)⊕f(x,y)(l≤x≤y≤r).
Define a function w(l,r)w(l,r) which returns \oplus g(x,y)(l \le x \le y \le r)⊕g(x,y)(l≤x≤y≤r).
You are also given a number of xor-queries. A xor-query is a pair (i, j) (1≤i≤j≤n). For each xor-query (i, j)(i,j), you have to answer the result of function w(l,r).
Input
Line 1: t(1≤t≤20).

For each test case:

Line 1: n(1≤n≤100000).

Line 2: n numbers a1, a2​ ,⋯,an(1≤ai≤10^9).

Line 33: q(1≤q≤100000), the number of xor-queries.

In the next q lines, each line contains 22 numbers i,j representing a xor-query(1≤i≤j≤n).

It is guaranteed that sum of nn and q≤10^6.

Output
For each xor-query (i, j)(i,j), print the result of function w(i,j)w(i,j) in a single line.

暴力打表找规律，维护前缀异或

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int b[4][maxn], c[4][maxn];
int dp1[4][maxn], dp2[4][maxn];
int main() {
	int T, n, m, l, r;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 1; j <= n; j++) {
				if(j%4==i)b[i][j] = 1;
				if(j%4==i) {
					c[i][j]=1;c[i][j + 1] = 1;
				}
			}
			for (int j = 1; j <= n; j++) {
				dp1[i][j] = dp1[i][j - 1] ^ (b[i][j] * a[j]);
				dp2[i][j] = dp2[i][j - 1] ^ (c[i][j] * a[j]);
			}
		}
		scanf("%d", &m);
		while (m--) {
			scanf("%d%d", &l, &r);
			int k = (r - l + 1) % 4;
			if (k == 0) {
				printf("0\n");
			} else if (k == 1) {
				for (int i = 0; i < 4; i++) {
					if(b[i][l]) {
						printf("%d\n", (dp1[i][l - 1] ^ dp1[i][r]));
						break;
					}
				}
			} else if (k == 3) {
				for (int i = 0; i < 4; i++) {
					if (b[i][l]==0 && b[i][l+1] == 1) {
						printf("%d\n", (dp1[i][l - 1] ^ dp1[i][r]));
						break;
					}
					
				}
			} else if (k == 2) {
				for (int i = 0; i < 4; i++) {
					if (c[i][l] == 1 && c[i][l + 1] == 1) {
						printf("%d\n", (dp2[i][l - 1] ^ dp2[i][r]));
						break;
					}
				}
			}
		}
		
		
	}
	return 0;
}
/* 11001100 01100110 00110011 10011001 1000 1000 1000 0100 0100 0100 0010 0010 0010 0001 0001 0001 */