#include<iostream>
#include<fstream>
#include <cassert>
#define f cin
#define mod 4001
#define g cout
#define N 50100
#define M 400100
#define lm 10
using namespace std;
int S[lm][M],D[lm][M],SOL[lm][M];
bool P[lm][M];
int i,n,m,x,p,nr,val,a,b,sol,X,t,j,T;
long long solutie,DR;
void up(int bit,int st,int dr,int po)
{
    if(st==dr)
    {
        P[bit][po]=x;
        return;
    }
    int mij=(st+dr)>>1;
    if(p<=mij)
    up(bit,st,mij,po<<1);
    else
    up(bit,mij+1,dr,(po<<1)+1);
    P[bit][po]=!(P[bit][po<<1]==P[bit][(po<<1)+1]);
}
void us(int bit,int st,int dr,int po)
{
    if(st==dr)
    {
        S[bit][po]=x;
        return ;
    }
    int mij=(st+dr)>>1;
    if(p<=mij)
    us(bit,st,mij,po<<1);
    else
    us(bit,mij+1,dr,(po<<1)+1);
    S[bit][po]=S[bit][po<<1];
    if(P[bit][po<<1])
    {
        nr=dr-mij;
        S[bit][po]+=nr-S[bit][(po<<1)+1];
    }
    else
    {
        S[bit][po]+=S[bit][(po<<1)+1];
    }
    S[bit][po]%=mod;
}
void ud(int bit,int st,int dr,int po)
{
    if(st==dr)
    {
        D[bit][po]=x;
        return ;
    }
    int mij=(st+dr)>>1;
    if(p<=mij)
    ud(bit,st,mij,po<<1);
    else
    ud(bit,mij+1,dr,(po<<1)+1);
    D[bit][po]=D[bit][(po<<1)+1];
    if(P[bit][(po<<1)+1])
    {
        nr=mij-st+1;;
        D[bit][po]+=nr-D[bit][po<<1];
    }
    else
    {
        D[bit][po]+=D[bit][po<<1];
    }
    D[bit][po]%=mod;
}
void u(int bit,int st,int dr,int po)
{
    if(st==dr)
    {
        SOL[bit][po]=x;
        return ;
    }
    int mij=(st+dr)>>1;
    if(p<=mij)
    u(bit,st,mij,po<<1);
    else
    u(bit,mij+1,dr,(po<<1)+1);
    val=SOL[bit][(po<<1)+1]+SOL[bit][po<<1];
    nr=dr-mij;
    val+=(int)D[bit][po<<1]*(nr-S[bit][(po<<1)+1])%mod;
    val%=mod;
    nr=mij-st+1;
    val+=(int)S[bit][(po<<1)+1]*(nr-D[bit][po<<1])%mod;
    val%=mod;
    while(val<0)
    val+=mod;
    while(val>=mod)
    val-=mod;
    SOL[bit][po]=val;
}
void find(int bit,int st,int dr,int po)
{
    if(st>=a&&dr<=b)
    {
        sol+=DR*(dr-st+1-S[bit][po]);
        sol+=(st-a-DR)*S[bit][po];
        sol+=SOL[bit][po];
        val=D[bit][po];
        if(P[bit][po])
        {
            nr=st-a;
            val+=(nr-DR);
        }
        else
            val+=DR;
        DR=val;
        sol%=mod;
        DR%=mod;
        return;
    }
    int mij=(st+dr)>>1;
    if(a<=mij)
    find(bit,st,mij,po<<1);
    if(b>mij)
    find(bit,mij+1,dr,(po<<1)+1);
}
int main ()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        p=i;
        f>>X;
        for(t=0,j=1;t<lm;j<<=1,t++)
        {
            if(X&j)
            x=1;
            else
            x=0;
            up(t,1,n,1);
            us(t,1,n,1);
            ud(t,1,n,1);
            u(t,1,n,1);
        }
    }
    for(i=1;i<=m;++i)
    {
        if(i==5)
        {
            i=i;
        }
        f>>T;
        if(T==1)
        {
               
            f>>p>>X;
assert(0<=x&&x<=1000);
assert(1<=p&&p<=n);
            for(t=0,j=1;t<lm;j<<=1,t++)
            {
                if(X&j)
                x=1;
                else
                x=0;
                up(t,1,n,1);
                us(t,1,n,1);
                ud(t,1,n,1);
                u(t,1,n,1);
            }
        }
        else
        {
assert(b<=100000);
assert(a<=b);
            f>>a>>b;
            solutie=0;
            for(t=0,j=1;t<lm;j<<=1,t++)
            {
            sol=DR=0;
            find(t,1,n,1);
            solutie+=sol*j%mod;
            if(solutie>=mod)
            solutie-=mod;
            }
            g<<solutie<<"\n";
 
        }
    }
    return 0;
}