#include <bits/stdc++.h>
using namespace std;

/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        while (c != ' ' && c != '\n' && c != '\r') {
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end

#define QwQ01AwA return 0
#define ll long long
#define look_time cerr << 1.0 * clock() / CLOCKS_PER_SEC << '\n'
template <typename T> void ckmax(T &x, T y) {x = max(x, y);}
template <typename T> void ckmin(T &x, T y) {x = min(x, y);}
#define ull unsigned long long

const ll inf = 1e18;
const int N = 5e5 + 5;
int n, m;
namespace Seg {
    const int B = 16;
    const int lim = 8;
    struct Tree {
        int ls, rs, len;
        ll mn, mx, tag;
        ull sum;
        void clear() {
            ls = rs = len = 0;
            mn = mx = tag = 0;
            sum = 0;
        }
    } t[N << 5];
    #define ls t[p].ls
    #define rs t[p].rs
    int stk[N << 5], top, cnt;
    inline int newnode() {
        if (!top) return ++cnt;
        else return t[stk[top]].clear(), stk[top--];
    }
    ll a[N];
    int rt[114];
    ll L[114], R[114];
    inline int gid(ll x) {return x <= 0 ? 0 : (__lg(x) / 4 + 1);}
    inline void up(int p) {
        if (!ls) {
            t[p].mn = t[rs].mn;
            t[p].mx = t[rs].mx;
            t[p].len = t[rs].len;
            t[p].sum = t[rs].sum;
        } else if (!rs) {
            t[p].mn = t[ls].mn;
            t[p].mx = t[ls].mx;
            t[p].len = t[ls].len;
            t[p].sum = t[ls].sum;
        } else {
            t[p].mn = min(t[ls].mn, t[rs].mn);
            t[p].mx = max(t[ls].mx, t[rs].mx);
            t[p].len = t[ls].len + t[rs].len;
            t[p].sum = t[ls].sum + t[rs].sum;            
        }
    }
    inline void push(int p, ll w) {
        t[p].sum += 1ull * w * t[p].len;
        t[p].tag += w;
        t[p].mx += w, t[p].mn += w;
    }
    inline void down(int p) {
        if (!t[p].tag) return ;
        if (ls) push(ls, t[p].tag);
        if (rs) push(rs, t[p].tag);
        t[p].tag = 0;
    }
    inline bool chk(ll x, int i) {
        if (!i) return x <= 0;
        return gid(x) == i;
    }
    inline void rebuild(int p, int l, int r, int id) {
        t[p].mx = -2e9, t[p].mn = 2e9;
        t[p].len = t[p].tag = t[p].sum = 0;
        for (int i = l; i <= r; i++) {
            if (!chk(a[i], id)) continue;
            t[p].len++;
            ckmin(t[p].mn, a[i]);
            ckmax(t[p].mx, a[i]);
            t[p].sum += a[i];
        }
    }
    inline void ins(int &p, int l, int r, int x, int nid) {
        if (!p) p = newnode();
        if (r - l + 1 <= 32) {
            for (int i = l; i <= r; i++) {
                if (!chk(a[i], nid)) continue;
                a[i] += t[p].tag;
            }
            a[x] -= t[p].tag;
            t[p].tag = 0;
            rebuild(p, l, r, nid);
            return ;
        }
        int mid = (l + r) / 2; down(p);
        if (x <= mid) ins(ls, l, mid, x, nid);
        else ins(rs, mid + 1, r, x, nid);
        up(p);
    }   
    inline void upd(int &p, int l, int r, int L, int R, int x, int nid) {
        if (!p) return ;
        if (t[p].mn == x && t[p].mx == x) return ;
        if (r - l + 1 <= 32) {
            for (int i = l; i <= r; i++) {
                if (!chk(a[i], nid)) continue;
                a[i] += t[p].tag;
            }
            t[p].tag = 0;
            // ckmax(L, l), ckmin(R, r);
            int st = max(L, l), ed = min(R, r);
            for (int i = st; i <= ed; i++) {
                if (!chk(a[i], nid)) continue;
                if (a[i] == x) continue;
                a[i] -= x;
                if (nid && a[i] < Seg::L[nid]) {
                    if (a[i] <= 0) ins(rt[0], 1, n, i, 0);
                    else ins(rt[gid(a[i])], 1, n, i, gid(a[i]));
                }
            }
            rebuild(p, l, r, nid);
            return ;
        }
        if (L <= l && r <= R && (!nid || t[p].mn - x >= Seg::L[nid])) return push(p, -x);
        int mid = (l + r) / 2; down(p);
        if (L <= mid) upd(ls, l, mid, L, R, x, nid);
        if (mid < R) upd(rs, mid + 1, r, L, R, x, nid);
        up(p);
        if (!t[p].len) stk[++top] = p, p = 0;
    }
    ull query(int p, int l, int r, int L, int R, int nid) {
        if (!p) return 0;
        if (r - l + 1 <= 32) {
            for (int i = l; i <= r; i++) {
                if (!chk(a[i], nid)) continue;
                a[i] += t[p].tag;
            }
            t[p].tag = 0;
            // ckmax(L, l), ckmin(R, r);
            int st = max(L, l), ed = min(R, r);
            ull res = 0;
            for (int i = st; i <= ed; i++) {
                if (!chk(a[i], nid)) continue;
                res += a[i];
            }
            return res;
        }
        if (L <= l && r <= R) return t[p].sum;
        int mid = (l + r) / 2; down(p);
        ull res = 0;
        if (L <= mid) res += query(ls, l, mid, L, R, nid);
        if (mid < R) res += query(rs, mid + 1, r, L, R, nid);
        return res;
    }
    inline void init() {
        // t[0].clear();
        ll pw = 1;
        for (int i = 1; i <= lim; i++) {
            L[i] = pw;
            R[i] = 1ll * pw * B - 1;
            pw *= B;
        }
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            ins(rt[gid(a[i])], 1, n, i, gid(a[i]));
        }
    }
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n >> m;
    Seg::init();
    int lst = 0;
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            l ^= lst, r ^= lst, x ^= lst;
            if (!x) continue;
            for (int i = 0; i <= Seg::lim; i++) Seg::upd(Seg::rt[i], 1, n, l, r, x, i);
        } else {
            int l, r;
            cin >> l >> r;
            l ^= lst, r ^= lst;
            ull ans = 0;
            for (int i = 0; i <= Seg::lim; i++) ans += Seg::query(Seg::rt[i], 1, n, l, r, i);
            lst = ans & ((1 << 20) - 1);
            cout << ans << endl;
        }
    }
    QwQ01AwA;
}

底层分块块长为 $1$ 是对的，块长不为 $1$ 就 WA55。

求和那里暴力递归到叶子节点也是对的。