#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=1<<20;
ll T[LIM], B[64];
ll pref[2*LIM];
bitset<64>lazy[2*LIM];
int tr[2*LIM][64], n, N=1;
void updpref(int l, int r, ll x) {
  l+=N; r+=N;
  pref[l]^=x;
  if(l!=r) pref[r]^=x;
  while(l/2!=r/2) {
    if(l%2==0) pref[l+1]^=x;
    if(r%2==1) pref[r-1]^=x;
    l/=2; r/=2;
  }
}
ll cntpref(int v) {
  v+=N;
  ll ans=0;
  while(v) {
    ans^=pref[v];
    v/=2;
  }
  return ans;
}
void spl(int v, int d, int k) {
  lazy[2*v][k].flip();
  lazy[2*v+1][k].flip();
  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].flip();
    }
    return;
  }
  rep(i, 64) if(lazy[v][i]) spl(v, (r-l+1)/2, 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)/2, 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) lazy[i].reset();
  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; else tr[N+i][j]=0;
  }
  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];
    pref[N+i+1]=pref[N+i]^T[i];
  }
  buduj();
  while(q--) {
    int t;
    cin >> t;
    if(t==1) {
      ll x, v;
      cin >> x >> v; --x;
      T[x]^=v;
      updpref(x+1, n, 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, h(cntpref(l))) << '\n';
    }
  }
}