#pragma GCC optimize("Ofast,fast-math")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int bmax = 64;
namespace Basis {
ull pivot[bmax];
ull contrmsk[bmax];
ull control = 0;
ull flippers = 0;
bool add(ull x) {
for(int i = bmax - 1; i >= 0; i--) {
if(pivot[i] == 0 && ((1ull << i) & x)) {
pivot[i] = x;
break;
}
else if(pivot[i] != 0 && ((1ull << i) & x))
x ^= pivot[i];
}
if(x == 0) return 0;
for(int i = 0; i < bmax; i++) {
if(pivot[i] == 0) continue;
for(int j = i + 1; j < bmax; j++) {
if(pivot[j] & (1ull << i))
pivot[j] ^= pivot[i];
}
}
control = 0;
flippers = 0;
for(int contra = 0; contra < bmax; contra++) {
contrmsk[contra] = 0;
if(pivot[contra] != 0) {
control |= (1ull << contra);
continue;
}
for(int i = contra + 1; i < bmax; i++)
if(pivot[i] & (1ull << contra)) contrmsk[contra] |= (1ull << i);
if(__builtin_popcountll(contrmsk[contra]) % 2 == 1)
flippers |= (1ull << contra);
}
return 1;
}
ull get_val(ull a) {
ull R = 0;
for(int i = 0; i < bmax; i++) {
if(pivot[i] != 0) continue;
R |= ((ull)((__builtin_popcountll(a & contrmsk[i]) & 1)
^ ((a & (1ull << i))? 1 : 0))) << i;
}
return R;
}
}
pii operator +(const pii& x, const pii& y) {
return pii{x.first + y.first, x.second + y.second};
}
pii flip(const pii& x) { return pii{x.second, x.first}; }
struct Node {
int cnt[bmax], len;
ull txor;
Node() {
for(int i = 0; i < bmax; i++) cnt[i] = 0;
len = 1;
txor = 0;
}
Node(ull a) {
for(int i = 0; i < bmax; i++) cnt[i] = 0;
len = 0;
txor = a;
}
void pull(const Node L, const Node R) {
for(int i = 0; i < bmax; i++) cnt[i] = L.cnt[i] + ((L.txor & (1ull << i))? R.len - R.cnt[i] : R.cnt[i]);
txor = L.txor ^ R.txor;
len = L.len + R.len;
}
};
template<typename Node>
struct AINT {
vector<Node> aint;
int n;
void init(int n_, Node TMP = Node()) {
n = n_;
aint.assign(2 * n + 5, TMP);
}
template<class CB> void walk(CB&& cb) { walk(cb, 1, n); }
template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 1, n); }
template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
walk(cb, l, r, L, cl, mid);
walk(cb, l, r, R, mid + 1, cr);
aint[node].pull(aint[L], aint[R]);
}
};
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, q;
cin >> n >> q;
AINT<Node> aint;
aint.init(n);
vector<ull> v(n + 1), real(n + 1);
for(auto &x : v | views::drop(1)) cin >> x;
real = v;
auto update = [&](int p, ull x) {
v[p] ^= Basis::get_val(x);
real[p] ^= x;
aint.walk([&](Node& val, int cl, int cr) {
val.pull(Node(v[cl]), Node());
return 0;
}, p, p);
};
auto reformat = [&]() {
for(int i = 1; i <= n; i++) v[i] = Basis::get_val(real[i]);
aint.walk([&](Node& val, int cl, int cr) {
if(cl != cr) return 1;
val.pull(Node(v[cl]), Node());
return 0;
});
return;
};
auto query = [&](int l, int r) -> ull {
ull rez = 0;
Node elem(Basis::flippers);
//elem.txor = Basis::flippers;
aint.walk([&](Node& val, int cl, int cr) {
elem.pull(elem, val);
return 0;
}, l, r);
for(int i = 0; i < bmax; i++)
rez += elem.cnt[i] * (1ull << i);
return rez;
};
reformat();
for(int i = 0; i < q; i++) {
int T;
cin >> T;
if(T == 1) {
int p;
ull x;
cin >> p >> x;
update(p, x);
}
else if(T == 2) {
ull x;
cin >> x;
if(Basis::add(x)) {
reformat();
}
}
else {
int l, r;
cin >> l >> r;
cout << query(l, r) + Basis::control * (ull)(r - l + 1) << '\n';
}
}
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/