#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;
}