#include <iostream>
using namespace std;

const int kMaxN = 100005, Mod = 4001;

struct AintNode {
	int a[10], b[10];
	bool sw[10];
	AintNode() {
		for (int i = 0; i < 10; ++i)
			a[i] = b[i] = sw[i] = 0;
	}
} aint[4 * kMaxN];

int el[kMaxN];

void make_under(int &nod, int &st, int &dr) {
	for (int i = 0; i < 10; ++i) {
		if (st == dr) {
			if (aint[nod].sw[i])
				aint[nod].a[i] = 0, aint[nod].b[i] = 1;
			else
 				aint[nod].a[i] = 1, aint[nod].b[i] = 0;
		} else {
			aint[nod].a[i] = aint[2 * nod].a[i] + aint[2 * nod + 1].a[i];
 			aint[nod].b[i] = aint[2 * nod].b[i] + aint[2 * nod + 1].b[i];   	
			if (aint[nod].sw[i])
				swap(aint[nod].a[i], aint[nod].b[i]);
		}
	}
	return ;
}

void aint_update(int nod, int st, int dr, int p, int el) {
	if (dr < p)
		return ;
	if (st >= p) {
		for (int i = 0; i < 10; ++i)
			if (el & (1 << i))
				aint[nod].sw[i] ^= 1;
		make_under(nod, st, dr);
		return ;
	}
	int m = (st + dr) / 2;
 	aint_update(2 * nod, st, m, p, el);
	aint_update(2 * nod + 1, m + 1, dr, p, el);
	make_under(nod, st, dr);
}

AintNode aint_query(int nod, int st, int dr, int c1, int c2) {
	if (c2 < st or dr < c1)
		return AintNode();
	if (c1 <= st and dr <= c2)
		return aint[nod];
	int m = (st + dr) / 2;
	AintNode rez = aint_query(2 * nod, st, m, c1, c2);
	AintNode rez2 = aint_query(2 * nod + 1, m + 1, dr, c1, c2);
	for (int i = 0; i < 10; ++i) {
		rez.a[i] += rez2.a[i];
		rez.b[i] += rez2.b[i];
		if (aint[nod].sw[i])
			swap(rez.a[i], rez.b[i]);
	}
	return rez;
}

void aint_make(int nod, int st, int dr) {
	for (int i = 0; i < 10; ++i)
		aint[nod].a[i] = (dr - st) + 1;
	if (st == dr)
		return ;
	int m = (st + dr) / 2;
	aint_make(2 * nod, st, m);
	aint_make(2 * nod + 1, m + 1, dr);
	return ;
}

int main() {
	int n, m;
	cin >> n >> m;
	aint_make(1, 0, n);
	for (int i = 1; i <= n; ++i) {
		cin >> el[i];
		aint_update(1, 0, n, i, el[i]);
	}
 	while (m--) {
		int t;
		cin >> t;
		if (t == 1) {
			int p, x;
			cin >> p >> x;
			aint_update(1, 0, n, p, el[p] ^ x);
			el[p] = x;
		} else {
			int a, b;
			cin >> a >> b;
 			AintNode rez = aint_query(1, 0, n, a - 1, b);
			int fi = 0;
			for (int i = 0; i < 10; ++i)
				fi = (fi + 1LL * (1 << i) * rez.a[i] * rez.b[i]) % Mod;
			cout << fi << '\n';
		}
	}
	return 0;
}