Problem Statement:

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 \leq i \leq r).
2. [2, l, r, x]: In this case, for each (arr[i]), (l \leq i \leq r), update the value to (arr[i] = arr[i] \, \oplus \, x) (where (\oplus) is the XOR operation).

Constraints:

1. (1 \leq N \leq 10^5)
2. (1 \leq Q \leq 10^5)
3. (1 \leq l \leq r \leq N)
4. (1 \leq x \leq 2^{30} — 1)

Approach:

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

For other updates, say multiply by (x), this would be simple. The value of ([l, r]) after the update would be:

[ \text{new_sum} = x \times \text{prev_sum} ]

For XOR updates, though, this is not so straightforward.

Simplifying the XOR Update:

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), which 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. The new sum is:

[ r — l + 1 — S ]

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

Generalizing for the Full Problem:

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 ( \log_{max} (=30) ) such arrays, and for each query:

1. For sum ([l, r]), calculate ( \text{sum}_0, \text{sum}_1, \ldots, \text{sum}_{29} ) for each of the trees. The final sum is:

[ \text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29} ]

1. For the update ([l, r]) with XOR (x), flip ([l, r]) for the (k^{th}) tree if the (k^{th}) 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;
}