#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 ApplyLz(int v) {
        if (seg[v].l != seg[v].r && seg[v].add) {
            int L = v << 1, R = v << 1 | 1;
            LL d = seg[v].add;
            seg[L].add += d;
            seg[L].sum += d * (seg[L].r - seg[L].l + 1);
            if (d & 1) swap(seg[L].odd_cnt, seg[L].even_cnt);
            seg[R].add += d;
            seg[R].sum += d * (seg[R].r - seg[R].l + 1);
            if (d & 1) swap(seg[R].odd_cnt, seg[R].even_cnt);
            seg[v].add = 0;
        }
        seg[v].lz  = true;
        seg[v].sum = seg[v].odd_cnt;
        seg[v].add = 0;
    }

    void PushDown(int u) {
        if (seg[u].lz) {
            ApplyLz(u << 1);
            ApplyLz(u << 1 | 1);
            seg[u].lz = false;
        }
        if (seg[u].add) {
            LL d = seg[u].add;
            int L = u << 1, R = u << 1 | 1;
            seg[L].add += d;
            seg[L].sum += d * (seg[L].r - seg[L].l + 1);
            if (d & 1) swap(seg[L].odd_cnt, seg[L].even_cnt);
            seg[R].add += d;
            seg[R].sum += d * (seg[R].r - seg[R].l + 1);
            if (d & 1) swap(seg[R].odd_cnt, seg[R].even_cnt);
            seg[u].add = 0;
        }
    }
    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 (l <= seg[u].l && seg[u].r <= r) {
            PushDown(u);
            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("mod2.in", "r", stdin);
    // freopen("mod2.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;
}