#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; struct data{ ll odd, even, sum; }; template struct LazySegmentTree{ private: int n; vector node; vector lazy; T E0; S E1; inline void updatef(S& lazy,S& value){ if(value==inf)lazy=inf; else lazy += value; } inline void calculatef(T& node,S& lazy,int len){ if(lazy>=inf){ node.sum = node.odd; node.sum += (lazy-inf)*len; if(lazy%2==0)swap(node.odd,node.even); } else { node.sum += lazy * len; if(lazy%2)swap(node.odd,node.even); } } inline T queryf(T& x,T& y){ return {x.odd+y.odd, x.even+y.even,x.sum+y.sum}; } public: LazySegmentTree(int sz,T nodeE,S lazyE ):E0(nodeE), E1(lazyE){ n=1; while(n& v,T E0,S E1 ):E0(E0),E1(E1){ n=1; int sz=v.size(); while(n=0; --i){ node[i] = queryf(node[2*i+1],node[2*i+2]); } } void eval(int k,int l,int r){ if(lazy[k]==E1)return ; calculatef(node[k], lazy[k], r-l); if(r-l>1){ updatef(lazy[2*k+1], lazy[k]); updatef(lazy[2*k+2], lazy[k]); } lazy[k]=E1; } void update(int a, int b, S x,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(r<=a||b<=l)return; if(a<=l&&r<=b){ updatef(lazy[k], x); eval(k,l,r); } else { update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); node[k]=queryf(node[2*k+1], node[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(r<=a||b<=l)return E0; if(a<=l&&r<=b)return node[k]; T xl=query(a,b,2*k+1,l,(l+r)/2); T xr=query(a,b,2*k+2,(l+r)/2,r); return queryf(xl, xr); } }; #define int long long signed main(){ int n,q; cin>>n>>q; vector a; rep(i,n){ int x; cin>>x; if(x%2)a.push_back({1,0,x}); else a.push_back({0,1,x}); } LazySegmentTree sg(a,{0,0,0},0); while(q--){ int t; cin>>t; if(t==1){ int l,r; cin>>l>>r; sg.update(--l,r,inf); } else if(t==2){ int l,r,x; cin>>l>>r>>x; sg.update(--l,r,x); } else { int l,r; cin>>l>>r; cout<