#pragma GCC optimize("Ofast")
#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]);
   }
};

const int nmax = 5e5 + 5;
const int Jump = 1000;
Node sage[nmax];
bool issage[nmax];

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;
      
      while(p >= 0 && issage[p] == 0) p--;
      if(p == -1) return;
      Node val(0);
      for(int i = p + Jump - 1; i >= p; i--) {
         Node here;
         here.pull(Node(v[i]), Node());
         val.pull(here, val);
      }
      sage[p] = val;
         
      
      //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]);
      
      Node val(0);
      int timer = 0;
      for(int i = n; i > 0; i--) {
         Node here;
         here.pull(Node(v[i]), Node());
         val.pull(here, val);
         timer++;
         if(timer == Jump) {
            issage[i] = 1;
            sage[i] = val;
            val = Node(0);
            timer = 0;
         }
         
         else
            issage[i] = 0;
      }
      
      //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;
      ull part = Basis::flippers;
      while(l <= r) {
         if(issage[l] && l + Jump - 1 <= r) {
            for(int i = 0; i < bmax; i++) 
               rez += (1ull << i) * ((part & (1ull << i))? sage[l].len - sage[l].cnt[i] : sage[l].cnt[i]);
            part ^= sage[l].txor;
            l += Jump;
            continue;
         }
         part ^= v[l];
         rez += part;
         l++;
      }
      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
*/