#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

typedef long long LL;

int n, q, a[N];

struct Node {
    int l, r;
    int odd_cnt, even_cnt;
    LL sum, add;
    bool lz;
};
struct SegTree {
    Node seg[N << 2];
    void PushUp(int u) {
        seg[u].odd_cnt = seg[u << 1].odd_cnt + seg[u << 1 | 1].odd_cnt;
        seg[u].even_cnt = seg[u << 1].even_cnt + seg[u << 1 | 1].even_cnt;
        seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
    }
    void PushDown(int u) {
        if (seg[u].lz) {
            seg[u << 1].lz = seg[u << 1 | 1].lz = true;
            seg[u << 1].sum = seg[u << 1].odd_cnt;
            seg[u << 1 | 1].sum = seg[u << 1 | 1].odd_cnt;
            seg[u << 1].add = seg[u << 1 | 1].add = 0;
            seg[u].lz = false;
        }
        if (seg[u].add) {
            seg[u << 1].add += seg[u].add;
            seg[u << 1].sum += seg[u].add * (seg[u << 1].r - seg[u << 1].l + 1);
            if (seg[u].add % 2) swap(seg[u << 1].odd_cnt, seg[u << 1].even_cnt);
            seg[u << 1 | 1].add += seg[u].add;
            seg[u << 1 | 1].sum += seg[u].add * (seg[u << 1 | 1].r - seg[u << 1 | 1].l + 1);
            if (seg[u].add % 2) swap(seg[u << 1 | 1].odd_cnt, seg[u << 1 | 1].even_cnt);
            seg[u].add = 0LL;
        }
    }
    void Build(int u, int l, int r) {
        seg[u] = { l, r, 0, 0, 0LL, 0LL, false };
        if (l == r) {
            if (a[l] % 2) ++seg[u].odd_cnt;
            else ++seg[u].even_cnt;
            seg[u].sum += a[l];
            return;
        }
        int mid = l + r >> 1;
        Build(u << 1, l, mid);
        Build(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void Unify(int u, int l, int r) {
        if (seg[u].l == seg[u].r) {
            seg[u].sum = seg[u].odd_cnt;
            seg[u].add = 0LL;
            seg[u].lz = false;
            return;
        }
        if (l <= seg[u].l && seg[u].r <= r) {
            if (!seg[u].lz) { // 推平操作前，没下传的 add 先下传
                seg[u << 1].add += seg[u].add;
                seg[u << 1 | 1].add += seg[u].add;
                seg[u << 1].sum += seg[u].add * (seg[u << 1].r - seg[u << 1].l + 1);
                seg[u << 1 | 1].sum += seg[u].add * (seg[u << 1 | 1].r - seg[u << 1 | 1].l + 1);
                if (seg[u].add % 2) {
                    swap(seg[u << 1].odd_cnt, seg[u << 1].even_cnt);
                    swap(seg[u << 1 | 1].odd_cnt, seg[u << 1 | 1].even_cnt);
                }
            }
            seg[u].lz = true;
            seg[u].sum = seg[u].odd_cnt;
            seg[u].add = 0LL;
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) Unify(u << 1, l, r);
        if (mid + 1 <= r) Unify(u << 1 | 1, l, r);
        PushUp(u);
    }
    void Add(int u, int l, int r, int x) {
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].add += x;
            seg[u].sum += 1LL * x * (seg[u].r - seg[u].l + 1);
            if (x % 2) swap(seg[u].odd_cnt, seg[u].even_cnt);
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) Add(u << 1, l, r, x);
        if (mid + 1 <= r) Add(u << 1 | 1, l, r, x);
        PushUp(u);
    }
    LL QuerySum(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].sum;
        PushDown(u);
        LL ret = 0LL;
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) ret += QuerySum(u << 1, l, r);
        if (mid + 1 <= r) ret += QuerySum(u << 1 | 1, l, r);
        return ret;
    }
} sgt;

int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sgt.Build(1, 1, n);

    for (int i = 1, op, l, r, x; i <= q; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &l, &r);
            sgt.Unify(1, l, r);
        } else if (op == 2) {
            scanf("%d%d%d", &l, &r, &x);
            sgt.Add(1, l, r, x);
        } else if (op == 3) {
            scanf("%d%d", &l, &r);
            printf("%lld\n", sgt.QuerySum(1, l, r));
        }
    }

    return 0;
}