#include int ri() { int n; scanf("%d", &n); return n; } struct SegTree { int n; struct Node { int64_t sum; int added; int compressed; int oddcnt; int l; int r; }; std::vector nodes; SegTree (const std::vector &a) { for (n = 1; n < (int) a.size(); n <<= 1); nodes.resize(n << 1); for (int i = 0; i < (int) a.size(); i++) nodes[i + n] = {a[i], 0, 0, a[i] & 1, i, i + 1}; for (int i = a.size(); i < n; i++) nodes[i + n] = {0, 0, 0, 0, i, i + 1}; for (int i = n - 1; i; i--) fetch(i); } void fetch(int i) { nodes[i].sum = nodes[i << 1].sum + nodes[i << 1 | 1].sum; nodes[i].oddcnt = nodes[i << 1].oddcnt + nodes[i << 1 | 1].oddcnt; nodes[i].l = nodes[i << 1].l; nodes[i].r = nodes[i << 1 | 1].r; } void flush(int i) { if (nodes[i].compressed) { if (nodes[i].compressed & 1) nodes[i].oddcnt = nodes[i].r - nodes[i].l - nodes[i].oddcnt, nodes[i].compressed = 1; else nodes[i].compressed = 2; nodes[i].sum = nodes[i].oddcnt; if (i < n) { nodes[i << 1].compressed += nodes[i].compressed; nodes[i << 1].compressed += nodes[i << 1].added & 1; nodes[i << 1].added = 0; nodes[i << 1 | 1].compressed += nodes[i].compressed; nodes[i << 1 | 1].compressed += nodes[i << 1 | 1].added & 1; nodes[i << 1 | 1].added = 0; } nodes[i].compressed = 0; } if (nodes[i].added) { if (nodes[i].added & 1) nodes[i].oddcnt = nodes[i].r - nodes[i].l - nodes[i].oddcnt; nodes[i].sum += (int64_t) (nodes[i].r - nodes[i].l) * nodes[i].added; if (i < n) { nodes[i << 1].added += nodes[i].added; nodes[i << 1 | 1].added += nodes[i].added; } nodes[i].added = 0; } } void mod2(int l, int r, int node = 1) { flush(node); if (l >= nodes[node].r || r <= nodes[node].l) return; if (l <= nodes[node].l && r >= nodes[node].r) { nodes[node].compressed = 2; flush(node); } else { mod2(l, r, node << 1); mod2(l, r, node << 1 | 1); fetch(node); } } void add(int l, int r, int val, int node = 1) { flush(node); if (l >= nodes[node].r || r <= nodes[node].l) return; if (l <= nodes[node].l && r >= nodes[node].r) { nodes[node].added = val; flush(node); } else { add(l, r, val, node << 1); add(l, r, val, node << 1 | 1); fetch(node); } } int64_t sum(int l, int r, int node = 1) { flush(node); if (l >= nodes[node].r || r <= nodes[node].l) return 0; if (l <= nodes[node].l && r >= nodes[node].r) return nodes[node].sum; int64_t res = sum(l, r, node << 1) + sum(l, r, node << 1 | 1); fetch(node); return res; } }; int main() { int n = ri(), q = ri(); std::vector a(n); for (auto &i : a) i = ri(); SegTree tree(a); for (int i = 0; i < q; i++) { int t = ri(); int l = ri() - 1; int r = ri(); if (t == 1) tree.mod2(l, r); else if (t == 2) tree.add(l, r, ri()); else if (t == 3) printf("%lld\n", (long long) tree.sum(l, r)); } return 0; }