#include<stdio.h>
#include<vector>
#include<algorithm>

#define biti 10
#define maxdim 100005
#define mod 4001

using namespace std;

int n;
int a[maxdim],arb[biti][4*maxdim],change[biti][4*maxdim];

inline void propaga ( int *arb , int *change , const int &nod , const int &st , const int &dr ){
	
	if ( change[nod] ){
		int mij = (st+dr)>>1;
		
		if ( st != dr ){
			int nodst = nod<<1;
			int noddr = nodst|1;
			change[nodst] ^= 1;
			arb[nodst] = mij-st+1-arb[nodst];
			change[noddr] ^= 1;
			arb[noddr] = dr-mij-arb[noddr];
		}
		
		change[nod] = 0;
	}
}

void update ( int *arb , int *change , int nod , int st , int dr , int a , int b ){
	
	if ( a <= st && dr <= b ){
		change[nod] ^= 1;
		arb[nod] = dr-st+1-arb[nod];
		return ;
	}
	
	propaga(arb,change,nod,st,dr);
	
	int mij = (st+dr)>>1;
	int nodst = nod<<1;
	int noddr = nodst|1;
	
	if ( a <= mij ){
		update(arb,change,nodst,st,mij,a,b);
	}
	if ( b > mij ){
		update(arb,change,noddr,mij+1,dr,a,b);
	}
	
	arb[nod] = arb[nodst]+arb[noddr];
}

void query ( int *arb , int *change , int nod , int st , int dr , int &sol , int a , int b ){
	
	propaga(arb,change,nod,st,dr);
	
	if ( a <= st && dr <= b ){
		sol += arb[nod];
		return ;
	}
	
	int mij = (st+dr)>>1;
	int nodst = nod<<1;
	int noddr = nodst|1;
	
	if ( a <= mij ){
		query(arb,change,nodst,st,mij,sol,a,b);
	}
	if ( b > mij ){
		query(arb,change,noddr,mij+1,dr,sol,a,b);
	}
	
	arb[nod] = arb[nodst]+arb[noddr];
}

int main () {
	
	#ifndef ONLINE_JUDGE
	freopen("queries.in","r",stdin);
	freopen("queries.out","w",stdout);
	#endif
	
	int operations;
	scanf("%d %d",&n,&operations);
	
	int x;
	for ( int i = 1 ; i <= n ; ++i ){
		scanf("%d",&x);
		a[i] = x;
		
		for ( int b = 0 ; b < biti ; ++b ){
			if ( a[i] & (1<<b) ){
				update(arb[b],change[b],1,1,n,i,n);
			}
		}
	}
	
	int tip,y;
	while ( operations-- ){
		scanf("%d %d %d",&tip,&x,&y);
		
		if ( tip == 1 ){
			
			int prevValue = a[x]; a[x] = y;
			
			for ( int b = 0 ; b < biti ; ++b ){
				if ( (prevValue&(1<<b)) != (y&(1<<b)) ){
					
					update(arb[b],change[b],1,1,n,x,n);
				}
			}
		}
		else{
			
			int sol = 0; --x;
			for ( int b = 0 ; b < biti ; ++b ){
				
				int ones = 0;
				query(arb[b],change[b],1,1,n,ones,max(x,1),y);
				int zeros = y-x+1-ones;
				
				sol = (sol + 1LL*(1<<b)*ones*zeros)%mod;
			}
			
			printf("%d\n",sol);
		}
	}
	
	return 0;
}