/*
 * Ideea e urmatoarea: problema se rezolva separat pentru fiecare bit.
 * Tot de sub linie ii rezolvarea pentru un singur bit. Se executa pentru toti
 * ___________________________________________________________________________
 * Un query ne cere sa vedem in cate subsecvente cuprinse intre A si B
 * apare bitul curent de numar impar de ori. Acest lucru il putem afla facand
 * produsul dintre numarul pozitiilor din interval a caror suma partiala este para
 * si numarul pozitiilor pentru care suma partiala este impara. 
 * Vom folosi un arbore de intervale pentru a afla aceste lucruri. Update-ul este pe
 * interval cu lazy update(se va face swap intre par si impar
 */
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAX = 100100;
const int MOD = 4001;
const int BIT_MAX = 11;
const bool DEBUG = false;

#define leftSon (nod << 1)
#define rightSon ((nod << 1) | 1)

int N, M;
int V[MAX], A[MAX];

struct ARB_INT {
    int parity[2];
    bool shallUpdate;
} aInt[BIT_MAX][MAX << 2];

void BuildAInt(ARB_INT aInt[], int nod, int L, int R) {
    if(L == R) {
        aInt[nod].parity[0]++;
        return;
    }
    int M = (L + R) >> 1;
    BuildAInt(aInt, leftSon, L, M);
    BuildAInt(aInt, rightSon, M + 1, R);

    for(int i = 0; i < 2; i++) 
        aInt[nod].parity[i] = aInt[leftSon].parity[i] + aInt[rightSon].parity[i];
}

void sendUpdate(ARB_INT aInt[], int nod) {
    if(!aInt[nod].shallUpdate)
        return;
    
    aInt[nod].shallUpdate = false;
    
    aInt[leftSon].shallUpdate ^= 1;
    swap(aInt[leftSon].parity[0], aInt[leftSon].parity[1]);

    aInt[rightSon].shallUpdate ^= 1;
    swap(aInt[rightSon].parity[0], aInt[rightSon].parity[1]);
}

void Update(ARB_INT aInt[], int nod, int L, int R, int Left, int Right) {
    if(L < R)
        sendUpdate(aInt, nod);
    if(Left <= L && R <= Right) {
        aInt[nod].shallUpdate ^= 1;
        swap(aInt[nod].parity[0], aInt[nod].parity[1]);
        return;
    }
    int M = (L + R) >> 1;
    if(Left <= M)
        Update(aInt, leftSon, L, M, Left, Right);
    if(Right > M) 
        Update(aInt, rightSon, M + 1, R, Left, Right);

    for(int i = 0; i < 2; i++)
        aInt[nod].parity[i] = aInt[leftSon].parity[i] + aInt[rightSon].parity[i];
}

int Query(ARB_INT aInt[], int nod, int L, int R, int Left, int Right, int Value) {
    if(L < R) 
        sendUpdate(aInt, nod);
    if(Left <= L && R <= Right) 
        return aInt[nod].parity[Value];
    int M = (L + R) >> 1, Ans = 0;
    if(Left <= M) 
        Ans += Query(aInt, leftSon, L, M, Left, Right, Value);
    if(Right > M)
        Ans += Query(aInt, rightSon, M + 1, R, Left, Right, Value);
    return Ans;
}

void afisare(ARB_INT aInt[], int nod, int L, int R) {
    cerr << "Nodul " << nod << " corespunde intervalului " << L << ", " << R << " si contine:\n";
    cerr << aInt[nod].parity[0] << " sume pare si " << aInt[nod].parity[1] << " sume impare\n";
    cerr << "And it should ";
    if(!aInt[nod].shallUpdate)
        cerr << "not ";
    cerr << "be updated\n\n";
    if(L < R) {
        int M = (L + R) >> 1;
        afisare(aInt, leftSon, L, M);
        afisare(aInt, rightSon, M + 1, R);
    }
}

void changeElement(int Position, int Value) {
    for(int bit = 0; bit < BIT_MAX; bit++) {
        if((Value & (1 << bit)) != (V[Position] & (1 << bit)))
            Update(aInt[bit], 1, 1, N + 1, Position + 1, N + 1);
    }
    V[Position] = Value;
}

int main() {
    if(DEBUG) {
        freopen("queries.in", "r", stdin);
        freopen("queries.out", "w", stdout);
        freopen("debug.out", "w", stderr);
    }
    //Reading initial vector
    cin >> N >> M;
 
    for(int i = 0; i < BIT_MAX; i++)
        BuildAInt(aInt[i], 1, 1, N + 1); 
    for(int i = 1, X; i <= N; i++) {
        cin >> X;
        changeElement(i, X);
    } 
    //Solving this
    /*if(DEBUG) 
        afisare(aInt[0], 1, 1, N + 1);
    */
    for(int i = 1, tip, A, B; i <= M; i++) {
        cin >> tip >> A >> B;
        if(tip == 1) { //Elementul de pe pozitia A devine B
            changeElement(A, B);
            /*if(DEBUG && i == 2)
                afisare(aInt[0], 1, 1, N + 1);
            */
            } else{  //Query pe intervalul A, B 
            int Ans = 0;
            for(int bit = 0; bit < BIT_MAX; bit++) {
                int Par = Query(aInt[bit], 1, 1, N + 1, A, B + 1, 0);
                int Impar = Query(aInt[bit], 1, 1, N + 1, A, B + 1, 1);
                Ans = (Ans + (1 << bit) * Par * Impar) % MOD;
                if(DEBUG && i == 3) {
                    cerr << "Pentru bitul " << bit << " am avut " << Par << " ";
                    cerr << "biti pari si " << Impar << " biti impari\n\n";
                }
            } cout << Ans << "\n";
        }
    }
    if(DEBUG) {
        fclose(stdin);
        fclose(stdout);
    }
}