Sequence

Oldjang has a sequence A of length n, the i_th number in which is A_i . He defined a function (f(l,r) = a_l⊕a_{l+1}⊕dots ⊕a_r).
It is simple for the cleverest boy oldjang to calculate the function, so he wants to make the problem

more difficult for fun. He will perform two operations:

The operation expressed as "0 x y", which means he changes the x_th number to y;

The operation expressed as "1 l r", which means he wants to calculate the function(F(l,r) =f(l,l)⊕f(l,l+1)⊕⋯⊕f(l,r)⊕f(l+1,l+1)⊕⋯f(l+1,r)⊕⋯⊕f(r,r)).

That means (F(l,r)) equals to the x or sum of all (f(i,j)) satisfied (lle ile jle r).

Oldjang thinks the problem is still too simple for him, so he gives this task to you.

Input

The first line contains a integers (T(1 le T le 10))— the number of test cases .

The second line contains two integers (n,m(1 le n,m le 10^5)), which means the sequence has

n numbers and oldjang has mm operations.

The next line contains nn integers — the sequence A.

In the following mm lines, each line contains three integers "0 x y" or "1l r" ,descriping a

operation.

Output

For each test case, print one line containing "Case # xx: " first, where xx is the test case number

(starting from 1).

Then output the answer after each the operations of second type.

样例输入

样例输出

Case #1:  
2
2

首先，(f(l,l)=a_l),题目上没说，但是看样例能看出来，令(len=r-l+1)，在(F)中，(a_{r-x})这个数异或了((x+1)(len-x))次，当(len)为偶数时，不论(x)是奇数还是偶数，(a_{r-x}) 异或了偶数次，为0。当(len)为奇数时，只有与(r)奇偶性相同的才异或了奇数次，即
(ans=a_l ⊕ a_{l+2}⊕dots ⊕a_{r-2} ⊕ a_r)
op操作是单点修改，维护奇偶两个树状数组就够了。
代码：

#include<bits/stdc++.h>
using namespace std;
char buf[100000],*L=buf,*R=buf;
#define gc() L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++
template<typename T>
inline void read(T&x) {
    int flag=x=0;
    char ch=gc();
    while (ch<'0'||ch>'9')
        flag|=ch=='-',ch=gc();
    while (ch>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+ch-48,ch=gc();
    if(flag)
        x=-x;
}
#define Init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f,mod=1e9+7,MAXN=5e4+8;
typedef long long ll;
int ji[MAXN],ou[MAXN],val[MAXN*2],n,m;
//分别是奇偶前缀异或
//1^ 3 ^5……和2^ 4 ^6……
inline int lowbit(int x) {return x & (-x);}
inline void build(int x,int add,int a[]) {//build 和change要分开写
    while(x<=MAXN) {
        a[x]^=add;
        x+=lowbit(x);
    }
}
inline void change(int x,int val,int a[],int pre) {//pre是这个位置原来的值，异或两次只有就为0
    while(x<=MAXN) {
        a[x]^=val;
        a[x]^=pre;
        x+=lowbit(x);
    }
}
inline int sum(int x,int a[]) {
    int ret=0;
    while(x!=0) {
        ret^=a[x];
        x-=lowbit(x);
    }
    return ret;
}
int main() {
    int t;
    read(t);
    for(int T=0; T<t; ++T) {
        printf("Case #%d:  
",T+1);
        Init(ji,0);
        Init(ou,0);//不初始化就挂了
        read(n),read(m);
        for(int i=1; i<=n; ++i) {
            read(val[i]);
            if(i&1)build(i/2+1,val[i],ji);//奇数
            else build(i/2,val[i],ou);
        }
        while(m--) {
            int op,x,y;
            read(op),read(x),read(y);
            if(op) {
                if((y-x+1)%2==0){printf("0
");continue;}//len&2==0 则为0
                int ans;
                if(y&1)ans=sum(y/2+1,ji)^sum(x/2,ji);//y是奇数
                else ans=sum(y/2,ou)^sum(x/2-1,ou);
                printf("%d
",ans);
            } else {
                if(x&1)change(x/2+1,y,ji,val[x]);
                else change(x/2,y,ou,val[x]);
                val[x]=y;//别忘了改。。。。。。。。
            }
        }
    }
    return 0;
}