#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define MAXN 100005
#define MOD 4001

int N, Q;
int A[MAXN];
int prefix[4 * MAXN][10][2];
int sufix[4 * MAXN][10][2];
int any[4 * MAXN][10];
int sum[4 * MAXN][10];

void init(int k, int st, int dr) {
    if(st == dr) {
        for(int bit = 0; bit < 10; bit++) {
            if(A[st] & (1 << bit)) {
                prefix[k][bit][1] = 1;
                sufix[k][bit][1] = 1;
                sum[k][bit] = 1;
                any[k][bit] = 1;
            }
            else {
                prefix[k][bit][0] = 1;
                sufix[k][bit][0] = 1;
            }
//            if(bit < 3) {
//                cerr << "range [" << st << "," << dr << "] bit " << bit << "\n";
//                cerr << "parity: " << sum[k][bit] << '\n';
//                cerr << "any: " << any[k][bit] << '\n';
//                for(int t = 0; t < 2; t++) {
//                    cerr << "prefix t=" << t << ": " << prefix[k][bit][t] << '\n';
//                    cerr << "sufix t=" << t << ": " << sufix[k][bit][t] << '\n';
//                }
//                cerr << endl;
//            }
        }
        return;
    }
    
    int m = (st + dr) / 2;
    init(2 * k, st, m);
    init(2 * k + 1, m + 1, dr);
    
    for(int bit = 0; bit < 10; bit++) {
        sum[k][bit] = sum[2 * k][bit] ^ sum[2 * k + 1][bit];
        any[k][bit] = any[2 * k][bit] + any[2 * k + 1][bit];
        
        for(int t = 0; t < 2; t++) {
            int tt = sum[2 * k][bit];
            int dt = abs(t - tt);
            prefix[k][bit][t] = (prefix[2 * k][bit][t] + prefix[2 * k + 1][bit][dt]) % MOD;
            
            tt = sum[2 * k + 1][bit];
            dt = abs(t - tt);
            sufix[k][bit][t] = (sufix[2 * k + 1][bit][t] + sufix[2 * k][bit][dt]) % MOD;
        }
        
        any[k][bit] += sufix[2 * k][bit][0] * prefix[2 * k + 1][bit][1];
        any[k][bit] += sufix[2 * k][bit][1] * prefix[2 * k + 1][bit][0];
        any[k][bit] %= MOD;
        
//        if(bit < 1) {
//            cerr << "range [" << st << "," << dr << "] bit " << bit << "\n";
//            cerr << "parity: " << sum[k][bit] << '\n';
//            cerr << "any: " << any[k][bit] << '\n';
//            for(int t = 0; t < 2; t++) {
//                cerr << "prefix t=" << t << ": " << prefix[k][bit][t] << '\n';
//                cerr << "sufix t=" << t << ": " << sufix[k][bit][t] << '\n';
//            }
//            cerr << endl;
//        }
    }
}

// parity
// prefix
// sufix
// any
void query(int k, int st, int dr, int L, int R, int bit, int ret[4][2]) {
    if(L <= st && dr <= R) {
        ret[0][0] = sum[k][bit];
        ret[3][0] = any[k][bit];
        for(int t = 0; t < 2; t++) {
            ret[1][t] = prefix[k][bit][t];
            ret[2][t] = sufix[k][bit][t];
        }
//        if(bit < 2) {
//            cerr << "range [" << st << "," << dr << "] bit " << bit << "\n";
//            cerr << "parity: " << ret[0][0] << '\n';
//            cerr << "any: " << ret[3][0] << '\n';
//            for(int t = 0; t < 2; t++) {
//                cerr << "prefix t=" << t << ": " << ret[1][t] << '\n';
//                cerr << "sufix t=" << t << ": " << ret[2][t] << '\n';
//            }
//            cerr << endl;
//        }
        return;
    }
    
    memset(ret, 0, 8 * sizeof(int));
    int m = (st + dr) / 2;
// parity
// prefix 2
// sufix 2
// any
    int auxL[4][2];
    int auxR[4][2];
    if(L <= m && R > m) {
        query(2 * k, st, m, L, R, bit, auxL);
        query(2 * k + 1, m + 1, dr, L, R, bit, auxR);
        
        ret[0][0] = auxL[0][0] ^ auxR[0][0];
        ret[3][0] = auxL[3][0] + auxR[3][0];
        
        for(int t = 0; t < 2; t++) {
            int tt = auxL[0][0];
            int dt = abs(t - tt);
            ret[1][t] = (auxL[1][t] + auxR[1][dt]) % MOD;
            
            tt = auxR[0][0];
            dt = abs(t - tt);
            ret[2][t] = (auxR[2][t] + auxL[2][dt]) % MOD;
        }
        
        ret[3][0] += auxL[2][0] * auxR[1][1];
        ret[3][0] += auxL[2][1] * auxR[1][0];
        ret[3][0] %= MOD;
        
//        if(bit < 2) {
//            cerr << "range [" << st << "," << dr << "] bit " << bit << "\n";
//            cerr << "parity: " << ret[0][0] << '\n';
//            cerr << "any: " << ret[3][0] << '\n';
//            for(int t = 0; t < 2; t++) {
//                cerr << "prefix t=" << t << ": " << ret[1][t] << '\n';
//                cerr << "sufix t=" << t << ": " << ret[2][t] << '\n';
//            }
//            cerr << endl;
//        }
    }
    else if(L <= m) {
        query(2 * k, st, m, L, R, bit, auxL);
        memcpy(ret, auxL, 8 * sizeof(int));
    }
    else if(R > m) {
        query(2 * k + 1, m + 1, dr, L, R, bit, auxR);
        memcpy(ret, auxR, 8 * sizeof(int));
    }
}

void update(int k, int st, int dr, int pos, int val) {
    if(st == dr) {
        A[st] = val;
        memset(prefix[k], 0, sizeof(prefix[k]));
        memset(sufix[k], 0, sizeof(sufix[k]));
        memset(sum[k], 0, sizeof(sum[k]));
        memset(any[k], 0, sizeof(any[k]));
        for(int bit = 0; bit < 10; bit++) {
            if(A[st] & (1 << bit)) {
                prefix[k][bit][1] = 1;
                sufix[k][bit][1] = 1;
                sum[k][bit] = 1;
                any[k][bit] = 1;
            }
            else {
                prefix[k][bit][0] = 1;
                sufix[k][bit][0] = 1;
            }
        }
        return;
    }
    
    int m = (st + dr) / 2;
    if(pos <= m)
        update(2 * k, st, m, pos, val);
    else
        update(2 * k + 1, m + 1, dr, pos, val);
    
    for(int bit = 0; bit < 10; bit++) {
        sum[k][bit] = sum[2 * k][bit] ^ sum[2 * k + 1][bit];
        any[k][bit] = any[2 * k][bit] + any[2 * k + 1][bit];
        
        for(int t = 0; t < 2; t++) {
            int tt = sum[2 * k][bit];
            int dt = abs(t - tt);
            prefix[k][bit][t] = (prefix[2 * k][bit][t] + prefix[2 * k + 1][bit][dt]) % MOD;
            
            tt = sum[2 * k + 1][bit];
            dt = abs(t - tt);
            sufix[k][bit][t] = (sufix[2 * k + 1][bit][t] + sufix[2 * k][bit][dt]) % MOD;
        }
        
        any[k][bit] += sufix[2 * k][bit][0] * prefix[2 * k + 1][bit][1];
        any[k][bit] += sufix[2 * k][bit][1] * prefix[2 * k + 1][bit][0];
        any[k][bit] %= MOD;
    }
}

int main() {
//	freopen("date.in", "r", stdin);
//	freopen("date.out","w", stdout);
	
	scanf("%d", &N);
	scanf("%d", &Q);	
	for(int i = 0; i < N; i++)
        scanf("%d", &A[i]);
	
	init(1, 0, N - 1);
	
	for(int i = 0; i < Q; i++) {
	    static int t, a, b;
        scanf("%d %d %d", &t, &a, &b);
        
        if(t == 1) {
            a--;
            update(1, 0, N - 1, a, b);
        }
        else {
            a--; b--;
            int ret[4][2];
            int q = 0;
            for(int i = 0; i < 10; i++) {
                query(1, 0, N - 1, a, b, i, ret);
                q += (int)ret[3][0] << i;
                q %= MOD;
            }
            printf("%d\n", q);
        }
	}
	
//	N = 10;
//	Q = 10;
//	
//	for(int i = )
		
	return 0;
}