#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef unsigned long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
ll T[LIM], B[64];
int tr[4*LIM][64], lazy[4*LIM][64], n, N=1;
void spl(int v, int d, int k) {
  lazy[2*v][k]^=lazy[v][k];
  lazy[2*v+1][k]^=lazy[v][k];
  tr[2*v][k]=d-tr[2*v][k];
  tr[2*v+1][k]=d-tr[2*v+1][k];
  lazy[v][k]=0;
}
void upd(int v, int l, int r, int a, int b, ll k) {
  if(b<l || r<a) return;
  if(a<=l && r<=b) {
    rep(i, 64) if(k&((ll)1<<(ll)i)) {
      tr[v][i]=(r-l+1)-tr[v][i];
      lazy[v][i]^=1;
    }
    return;
  }
  rep(i, 64) if(lazy[v][i]) spl(v, r-l+1, i);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, k);
  upd(2*v+1, mid+1, r, a, b, k);
  rep(i, 64) tr[v][i]=tr[2*v][i]+tr[2*v+1][i];
}
ll cnt(int v, int l, int r, int a, int b, ll k) {
  if(b<l || r<a) return 0;
  if(a<=l && r<=b) {
    ll ans=0;
    rep(i, 64) if(k&((ll)1<<(ll)i)) ans+=(ll)(r-l+1-tr[v][i])<<(ll)i; else ans+=(ll)tr[v][i]<<(ll)i;
    return ans;
  }
  rep(i, 64) if(lazy[v][i]) spl(v, r-l+1, i);
  int mid=(l+r)/2;
  return cnt(2*v, l, mid, a, b, k)+cnt(2*v+1, mid+1, r, a, b, k);
}
bool updb(ll x) {
  for(int i=63; i>=0; --i) x=min(x, x^B[i]);
  for(int i=63; i>=0; --i) if(x&((ll)1<<(ll)i)) {
    B[i]=x;
    return true;
  }
  return false;
}
ll g(ll x) {
  for(int i=63; i>=0; --i) x=max(x, x^B[i]);
  return x;
}
ll h(ll x) {
  for(int i=63; i>=0; --i) x=min(x, x^B[i]);
  return x;
}
void buduj() {
  rep(i, 2*N) rep(j, 64) tr[i][j]=lazy[i][j]=0;
  ll x=0;
  rep(i, n) {
    x^=T[i];
    ll p=g(x);
    rep(j, 64) if(p&((ll)1<<(ll)j)) tr[N+i][j]=1;
  }
  for(int i=N-1; i; --i) rep(j, 64) tr[i][j]=tr[2*i][j]+tr[2*i+1][j];
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int q;
  cin >> n >> q;
  while(N<n) N*=2;
  rep(i, n) cin >> T[i];
  buduj();
  while(q--) {
    int t;
    cin >> t;
    if(t==1) {
      ll x, v;
      cin >> x >> v; --x;
      T[x]^=v;
      upd(1, 0, N-1, x, n-1, h(v));
    } else if(t==2) {
      ll x;
      cin >> x;
      if(updb(x)) buduj();
    } else {
      int l, r;
      cin >> l >> r; --l; --r;
      cout << cnt(1, 0, N-1, l, r, 0) << '\n';
    }
  }
}