#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXK 21

int n, m, lans;

namespace Trie{
    struct Node{int s[2], fa, v, tg, c;};
    vector<Node> tr(1, {{0, 0}, 0, 0, 0, 0});
    void insert(int x, int y){
        for (int i(0), p(0); i<MAXK; ++i){
            tr[p].v += x;
            ++tr[p].c;
            if (!tr[p].s[(y>>i)&1]){
                tr[p].s[(y>>i)&1] = tr.size();
                tr.push_back({{0, 0}, p, 0, 0, 0});
            }
            p = tr[p].s[(y>>i)&1];
        }
    }
    void push_up(int p, int v){
        tr[p].v += v;
        if (p) push_up(tr[p].fa, v);
    }
    void add_tag(int p, int s){
        if (p){
            tr[p].tg += s;
            tr[p].v += s * tr[p].c;
        }
    }
    void modify(int x, int y, int z){
        int p(0);
        for (int i(0); i<x; p=tr[p].s[(y>>(i++))&1]);
        push_up(p, tr[p].c*z);
        tr[p].tg += z;
    }
    int query(int x, int y){
        int p(0);
        for (int i(0); i<x; ++i){
            if (!tr[p].s[(y>>i)&1]) return 0;
            if (tr[p].tg){
                add_tag(tr[p].s[0], tr[p].tg);
                add_tag(tr[p].s[1], tr[p].tg);
                tr[p].tg = 0;
            }
            p = tr[p].s[(y>>i)&1];
        }
        return tr[p].v;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i(1), x; i<=n; ++i){
        cin >> x;
        Trie::insert(x, i);
    }

    for (int opt, x, y, z; m; --m){
        cin >> opt >> x >> y;
        opt = (opt+lans)%2+1;
        if (opt == 1){
            cin >> z;
            Trie::modify(x, y, z);
        }else cout << (lans=Trie::query(x, y)) << '\n';
    }

    return 0;
}