#include <iostream>
#include <cstdio>
#define f cin
#define g cout
#define NM 100010

using namespace std;

int N, M;
int A[NM];
const int MOD=4001;
int L, R;
int par, imp;

struct data
{
    int sum[2];
    bool sendinfo;
} AI[10][4*NM];

void Build (data AI[], int node, int S, int D)
{
    if (S>=D)
    {
        AI[node].sum[0]++;
        return;
    }
    int M=(S+D)/2;

    Build(AI, 2*node, S, M);
    Build(AI, 2*node+1, M+1, D);

    for (int w=0; w<2; w++)
        AI[node].sum[w] = AI[2*node].sum[w] + AI[2*node+1].sum[w];
}

void Send (data AI[], int node)
{
    if (AI[node].sendinfo==0)
        return;

    AI[node].sendinfo=0;

    for (int w=0; w<=1; w++)
    {
        swap(AI[2*node + w].sum[0], AI[2*node + w].sum[1]);
        AI[2*node + w].sendinfo^=1;
    }
}

void Swap (data AI[], int node, int S, int D)
{
    if (S<D)
        Send(AI, node);

    if (L<=S && D<=R)
    {
        swap(AI[node].sum[0], AI[node].sum[1]);
        AI[node].sendinfo^=1;
        return;
    }

    int M=(S+D)/2;

    if (L<=M)
        Swap(AI, 2*node, S, M);
    if (R>M)
        Swap(AI, 2*node+1, M+1, D);

    for (int w=0; w<2; w++)
        AI[node].sum[w] = AI[2*node].sum[w] + AI[2*node+1].sum[w];
}

void Query (data AI[], int node, int S, int D)
{
    if (S<D)
        Send(AI, node);

    if (L<=S && D<=R)
    {
        par+=AI[node].sum[0];
        imp+=AI[node].sum[1];
        return;
    }

    int M=(S+D)/2;
    if (L<=M)
        Query(AI, 2*node, S, M);
    if (R>M)
        Query(AI, 2*node+1, M+1, D);
}

void Put (int p, int x)
{
    for (int b=0; b<10; b++)
    {
        if (((A[p]^x)&(1 << b))==0)
            continue;

        L=p+1;
        R=N+1;
        Swap(AI[b], 1, 1, N+1);
    }

    A[p]=x;
}

int Solve (int l, int r)
{
    int ANS=0;

    L=l;
    R=r+1;

    for (int b=0; b<10; b++)
    {
        par=imp=0;
        Query(AI[b], 1, 1, N+1);

        ANS=(1LL * ANS + 1LL * par * imp * (1 << b))%MOD;
    }

    return ANS;
}

int main()
{
   /* #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif */

    f >> N;
    f >> M;

    for (int b=0; b<10; b++)
        Build(AI[b], 1, 1, N+1);

    for (int i=1; i<=N; i++)
    {
        int x;
        f >> x;
        Put(i, x);
    }

    for (int i=1; i<=M; i++)
    {
        int t, a, b;
        f >> t >> a >> b;
        if (t==1)
            Put(a, b);
        else
            g << Solve(a, b) << '\n';
    }

    return 0;
}