Given a sequence of nn numbers a_1, a_2, \cdots, a_na1​,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, ji,j) (1 \le i \le j \le n1≤i≤j≤n). For each xor-query (i, j)(i,j), you have to answer the result of function w(l,r)w(l,r).

Input

Line 11: t (1 \le t \le 20)t(1≤t≤20).

For each test case:

Line 11: n (1 \le n \le 100000)n(1≤n≤100000).

Line 22: nn numbers a_1, a_2, \cdots, a_n (1 \le a_i \le 10^9)a1​,a2​,⋯,an​(1≤ai​≤109).

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

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

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

Output

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

样例输入复制

1
5
1 2 3 4 5
5
1 3
1 5
1 4
4 5
3 5

样例输出复制

2
4
0
1
4

        队友做的，我就偷偷放个题~~

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 1e5+5;

int ar[maxn];
int br[maxn];

int main ()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(br, 0, sizeof(br));
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &ar[i]);
        }
        for (int i = 1; i <= n; ++i) {
            if (i <= 4) {
                br[i] = ar[i];
            }
            else {
                br[i] = ar[i]^br[i-4];
            }
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            int l, r;
            scanf("%d %d", &l, &r);
            if ((r-l+1)%4 == 0) {
                cout << 0 << '\n';
            }
            else if ((r-l+1)%4 == 1) {
                int ans = br[r];
                if (l-4 >= 0) {
                    ans ^= br[l-4];
                }
                cout << ans << '\n';
            }
            else if ((r-l+1)%4 == 3) {
                int ans = br[r-1];
                if (l-3 >= 0) {
                    ans ^= br[l-3];
                }
                cout << ans << '\n';
            }
            else {
                int ans = br[r]^br[r-1];
                if (l-4 >= 0) {
                    ans ^= br[l-4];
                }
                if (l-3 >= 0) {
                    ans ^= br[l-3];
                }
                cout << ans << '\n';
            }
        }
    }
    return 0;
}