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 <= N <= 10 ** 5 1 <= Q <= 10 ** 5 1 <= l <= r <= N 1 <= x <= 2 ** 30 — 1

Approach:

#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;
}