#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) (void(0))
#endif

#include <atcoder/lazysegtree>
struct S {
    long long sum;
    long long odd, even;
};
S op(S a, S b) {
    return S{
        a.sum + b.sum,
        a.odd + b.odd,
        a.even + b.even,
    };
}
S e() {
    return S{0, 0, 0};
}

struct F {
    long long psum;
    int type;  // 0 -> add
    long long nsum;
};

F id() { return F{0, 0, 0}; }
S mapping(F f, S x) {
    if (f.type == 1) {
        if (f.psum & 1) swap(x.odd, x.even);
        S res = S{
            x.odd + f.nsum * (x.odd + x.even),
            x.odd,
            x.even};
        if (f.nsum & 1) swap(res.odd, res.even);
        return res;
    } else {
        S res = x;
        res.sum += f.nsum * (x.odd + x.even);
        if (f.nsum & 1) swap(res.odd, res.even);
        return res;
    }
}

F composition(F f, F g) {
    if (f.type == 1) {
        F res;
        res.psum = g.psum + g.nsum + f.psum;
        res.type = 1;
        res.nsum = f.nsum;
        return res;
    }
    g.nsum += f.nsum;
    return g;
}
void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<S> init(N);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        init[i] = S{a, a & 1, ~a & 1};
    }
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);
    while (Q--) {
        int o;
        cin >> o;
        if (o == 1) {
            int l, r;
            cin >> l >> r;
            seg.apply(l - 1, r, F{0, 1, 0});
        } else if (o == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            seg.apply(l - 1, r, F{0, 0, x});
        } else {
            int l, r;
            cin >> l >> r;
            S ans = seg.prod(l - 1, r);
            cout << ans.sum << endl;
        }
    }
}

int main() {
    int T = 1;
    // std::cin >> T;
    while (T--) {
        solve();
    }
}