#include using namespace std; using ll = long long; // #define int ll using PII = pair; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template T &chmin(T &a, const T &b) { return a = min(a, b); } template T &chmax(T &a, const T &b) { return a = max(a, b); } template bool IN(T a, T b, T x) { return a<=x&&x T ceil(T a, T b) { return a/b + !!(a%b); } template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a,Ts... ts) { return vector(ts...))>(a,make_v(ts...)); } template typename enable_if::value==0>::type fill_v(T &t, const V &v) { t=v; } template typename enable_if::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template ostream &operator <<(ostream& out,const pair& a) { out<<'('< ostream &operator <<(ostream& out,const vector& a){ out<<'['; for(const T &i: a) out< ostream &operator <<(ostream& out, const set& a) { out<<'{'; for(const T &i: a) out< ostream &operator <<(ostream& out, const map& a) { out<<'{'; for(auto &i: a) out< struct lazysegtree { using T = typename Monoid::T; using E = typename Monoid::E; int n, height; vector dat; vector lazy; lazysegtree() {} lazysegtree(int n_) { n = 1, height = 0; while(n < n_) { n *= 2; height++; } dat.assign(n*2, Monoid::dt()); lazy.assign(n*2, Monoid::de()); } void build(vector v) { REP(i, v.size()) dat[i+n] = v[i]; for(int i=n-1; i>0; --i) dat[i] = Monoid::f(dat[i*2], dat[i*2+1]); } inline T reflect(int k) { return lazy[k]==Monoid::de()?dat[k]:Monoid::g(dat[k], lazy[k]); } inline void eval(int k) { if(lazy[k] == Monoid::de()) return; lazy[2*k] = Monoid::h(lazy[k*2], lazy[k]); lazy[2*k+1] = Monoid::h(lazy[k*2+1], lazy[k]); dat[k] = reflect(k); lazy[k] = Monoid::de(); } inline void thrust(int k) { for(int i=height;i;--i) eval(k>>i); } inline void recalc(int k) { while(k>>=1) dat[k] = Monoid::f(reflect(k*2), reflect(k*2+1)); } void update(int a, int b, E x) { thrust(a+=n); thrust(b+=n-1); for(int l=a, r=b+1; l>=1,r>>=1) { if(l&1) lazy[l] = Monoid::h(lazy[l], x), ++l; if(r&1) --r, lazy[r] = Monoid::h(lazy[r], x); } recalc(a); recalc(b); } T query(int a, int b) { thrust(a+=n); thrust(b+=n-1); T vl=Monoid::dt(), vr=Monoid::dt(); for(int l=a, r=b+1; l>=1,r>>=1) { if(l&1) vl=Monoid::f(vl, reflect(l++)); if(r&1) vr=Monoid::f(reflect(--r), vr); } return Monoid::f(vl, vr); } friend ostream &operator <<(ostream& out,const lazysegtree& seg) { out << "---------------------" << endl; int cnt = 1; for(int i=1; i<=seg.n; i*=2) { REP(j, i) { out << "(" << seg.dat[cnt].sum << "," << seg.lazy[cnt].x1 << " " << seg.lazy[cnt].x2 << " " << seg.lazy[cnt].f << ") "; cnt++; } out << endl; } out << "---------------------" << endl; return out; } }; struct node { ll sum, sum2, len; node() : sum(0), sum2(0), len(0) {} node(ll a, ll b, ll c) : sum(a), sum2(b), len(c) {} }; struct op { ll x1, x2, f; op() : x1(0), x2(0), f(0) {} op(ll a, ll b, ll c) : x1(a), x2(b), f(c) {} bool operator==(op r) const { return (x1==r.x1 && x2==r.x2 && f==r.f); } }; struct linear_exp { using T = node; using E = op; static T dt() { return node(); } static E de() { return op(); } static T f(const T &a, const T &b) { node ret; ret.sum = a.sum + b.sum; ret.sum2 = a.sum2 + b.sum2; ret.len = a.len + b.len; return ret; } static T g(const T &a, const E &b) { node ret; if(b.f == 1) { ret.sum = (b.x1%2?a.len-a.sum2:a.sum2); ret.sum += b.x2*a.len; } else { ret.sum = a.sum+(b.x1+b.x2)*a.len; } ret.sum2 = (b.x1+b.x2)%2?a.len-a.sum2:a.sum2; ret.len = a.len; return ret; } static E h(const E &a, const E &b) { op ret; if(b.f == 1) { ret.x1 = a.x1 + a.x2 + b.x1; ret.x2 = b.x2; ret.f = 1; } else { ret.x1 = a.x1; ret.x2 = a.x2 + b.x1 + b.x2; ret.f = a.f; } return ret; } }; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, q; cin >> n >> q; vector a(n); REP(i, n) cin >> a[i]; lazysegtree seg(n); vector va(n); REP(i, n) va[i] = node(a[i], a[i]%2, 1); seg.build(va); while(q--) { ll type; cin >> type; if(type == 1) { ll l, r; cin >> l >> r; l--, r--; seg.update(l, r+1, op(0, 0, 1)); } else if(type == 2) { ll l, r, x; cin >> l >> r >> x; l--, r--; seg.update(l, r+1, op(x, 0, 0)); } else { ll l, r; cin >> l >> r; l--, r--; cout << seg.query(l, r+1).sum << endl; } // cout << seg << endl; } return 0; }