#include <cstdio> #include <algorithm> using namespace std; #define impar first.first #define par first.second #define sent second #define BIT 10 #define info pair < pair < int , int > , bool > #define lson(x) ((x)<<1) #define rson(x) (((x)<<1)|1) #define NMAX 100007 #define MOD 4001 info t[BIT][3*NMAX]; int N,Q,L,i,x,type,a,b,pos,R,top,toi; int v[NMAX]; void Build(info t[],int n,int l,int r) { if (l==r) { ++t[n].par; return ; } int m=(l+r)>>1; Build(t,lson(n),l,m); Build(t,rson(n),m+1,r); t[n].par=t[lson(n)].par+t[rson(n)].par; t[n].impar=t[lson(n)].impar+t[rson(n)].impar; } void Send(info t[],int n) { if (!t[n].sent) return ; t[n].sent=false; swap(t[lson(n)].par,t[lson(n)].impar); t[lson(n)].sent^=1; swap(t[rson(n)].par,t[rson(n)].impar); t[rson(n)].sent^=1; } void Swap(info t[],int n,int l,int r) { if (l<r) Send(t,n); if (L<=l && r<=R) { swap(t[n].par,t[n].impar); t[n].sent^=1; return ; } int m=(l+r)>>1; if (L<=m) Swap(t,lson(n),l,m); if (R>m) Swap(t,rson(n),m+1,r); t[n].par=t[lson(n)].par+t[rson(n)].par; t[n].impar=t[lson(n)].impar+t[rson(n)].impar; } void Query(info t[],int n,int l,int r) { if (l<r) Send(t,n); if (L<=l && r<=R) { top+=t[n].par; toi+=t[n].impar; return ; } int m=(l+r)>>1; if (L<=m) Query(t,lson(n),l,m); if (R>m) Query(t,rson(n),m+1,r); } void Update(int pos,int va) { int j; for (j=0;j<BIT;++j) { if ((v[pos]&(1<<j))==(va&(1<<j))) continue; L=pos+1; R=N+1; Swap(t[j],1,1,N+1); } v[pos]=va; } int get_ans(int l,int r) { int s=0,j; L=l; R=r+1; for (j=0;j<BIT;++j) { toi=top=0; Query(t[j],1,1,N+1); s=(s+(long long)toi*top*(1<<j))%MOD; } return s; } int main() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif scanf("%d%d",&N,&Q); for (i=0;i<BIT;++i) Build(t[i],1,1,N+1); for (i=1;i<=N;++i) { scanf("%d",&x); Update(i,x); } for (;Q;--Q) { scanf("%d",&type); if (type==1) { scanf("%d%d",&pos,&x); Update(pos,x); } else { scanf("%d%d",&a,&b); printf("%d\n",get_ans(a,b)); } } return 0; }