Consider the following problem: You are given an array arr of size N. Initially all arr[i] are set to 0. Now consider Q queries, where each query is of one of the following two types: 1. [1, l, r]: In this case calculate the sum of values of arr[i] for l <= i <= r. 2. [2, l, r, x]: In this case for each arr[i], l <= i <= r, update the value to arr[i] = arr[i] ^ x (where ^ is the XOR operation).

Constraints: 1. 1 <= N <= 10 ** 5 2. 1 <= Q <= 10 ** 5 3. 1 <= l <= r <= N 4. 1 <= x <= 2 ** 30 — 1

Approach: This problem can be solved easily with a Segment Tree with Lazy Propogation, had there been no XOR updates. Lazy Propogation requires that for an update on range [l, r], we should be able to calculate the value of [l, r] after update in O(1) time (or atleast sub-linear time like O(log n)).

For other updates, say multiply by x, this would be simple. The value of [l, r] after update would be new_sum = x * prev_sum

For XOR updates, though, this is not so straight forward.

Consider a simpler problem. Let's say that all values in arr can be either 0 or 1 and even x can be only 0 or 1. Now the sum of range [l, r] is S, indicates that there are S 1s and r — l + 1 — S 0s in [l, r]. 1. An update with x = 0, won't change anything. 2. An update with x = 1, would flip 0s and 1s, so there will be r — l + 1 — S 1s and S 0s. So new sum is r — l + 1 — S.

Thus we can build a segment tree with lazy propogation for this array.

The key idea is to notice that each number can be at most 30 bits and we can just maintain such arrays for each of the 30 bits.

So we build LOGMAX(=30) such arrays and for each query: 1. For sum [l, r], calculate sum0, sum1, ..., sum29 for each of the tree. Final sum is sum0 * 2 ** 0 + sum1 * 2 ** 1 + ... + sum29 * 2 ** 29. 2. For update [l, r] with xor x, flip [l, r] for kth tree if the kth bit of x is set.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
struct LazySegmentTree {
  int n;
  vector<ll> L, R;
  vector<int> val;
  vector<bool> lazy;

  LazySegmentTree(int sz) {
    n = 4 * sz;
    L.resize(n);
    R.resize(n);
    lazy.resize(n);
    val.resize(n);
    n >>= 1;
    init(1, 0, sz - 1);
  }

  void init(int node, int l, int r) {
    if (l > r) {
      return;
    }
    L[node] = l;
    R[node] = r;
    if (l < r) {
      int mid = (l + r) / 2;
      init(2 * node, l, mid);
      init(2 * node + 1, mid + 1, r);
    }
  }

  void flip(int node){
    lazy[node] = lazy[node] ^ 1;
    val[node] = (R[node] - L[node] + 1) - val[node]; // Updating sum for range
  }

  void propagate(int node) {
    if(L[node] < R[node]){
      if(lazy[node]){
        flip(2 * node);
        flip(2 * node + 1);
        lazy[node] = 0;
      }
    }
  }

  void set(int node, int l, int r) {
    if (r < L[node] || R[node] < l) {
      return;
    }
    if (l <= L[node] && R[node] <= r) {
      flip(node);
    } else {
      propagate(node);
      set(2 * node, l, r);
      set(2 * node + 1, l, r);
      val[node] = val[2 * node] + val[2 * node + 1];
    }
  }

  ll get(int node, int l, int r) {
    if (r < L[node] || R[node] < l) {
      return 0; // Out of range
    }
    if (l <= L[node] && R[node] <= r) {
      return val[node];
    }
    propagate(node);
    ll left_sum = get(2 * node, l, r);
    ll right_sum = get(2 * node + 1, l, r);
    return left_sum + right_sum;
  }
};

const int LOGMAX = 30;
 
vector<ll> solve(int n, vector<vector<int>> &queries) {
  vector<LazySegmentTree> tree;
  for(int k = 0; k < LOGMAX; ++k){
    tree.push_back(LazySegmentTree(n + 1));
  }
  vector<ll> res;
  for(vector<int> &query: queries){
    int type = query[0];
    if(type == 1){
      int l = query[1];
      int r = query[2];
      ll sum = 0;
      for(int k = 0; k < LOGMAX; ++k){
        sum += (1ll << k) * tree[k].get(1, l, r);
      }
      res.push_back(sum);
    }
    else{
      int l = query[1];
      int r = query[2];
      int x = query[3];
      for(int k = 0; k < LOGMAX; ++k){
        if(1 & (x >> k)){
          tree[k].set(1, l, r);
        }
      }
    }
  }
  return res;
}

vector<ll> brute(int n, vector<vector<int>> &queries) {
  vector<int> arr(n + 1);
  vector<ll> res;
  for(vector<int> &query: queries){
    int type = query[0];
    if(type == 1){
      int l = query[1];
      int r = query[2];
      ll sum = 0;
      for(int i = l; i <= r; ++i){
        sum += arr[i];
      }
      res.push_back(sum);
    }
    else{
      int l = query[1];
      int r = query[2];
      int x = query[3];
      for(int i = l; i <= r; ++i){
        arr[i] = arr[i] ^ x;
      }
    }
  }
  return res;
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n, q;
  cin >> n >> q;
  vector<vector<int>> queries(q);
  for(int i = 0; i < q; ++i){
    int type, l, r;
    cin >> type >> l >> r;
    queries[i] = {type, l, r};
    if(type == 2){
      int x;
      cin >> x;
      queries[i].push_back(x);
    }
  }

  for(ll elem: brute(n, queries)){
    cout << elem << '\n';
  }

  assert(solve(n, queries) == brute(n, queries));

  
  return 0;
}