#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 5e5+5; 
int n, m, a[N]; 

struct node {
    int l, r; 
    ll sa, mx, sb, ad, dx; 
}v[N*4]; 
ll gets (int p, ll k) {
    if (v[p].l == v[p].r) return max(k, v[p].mx); 
    if (k >= v[p<<1].mx) return k*(v[p<<1].r-v[p<<1].l+1)+gets(p<<1|1, k); 
    return gets(p<<1, k)+v[p].sa-v[p<<1].sa; 
}
inline void pa (int p) {
    v[p].sa = v[p<<1].sa+gets(p<<1|1, v[p<<1].mx);
    v[p].mx = max(v[p<<1].mx, v[p<<1|1].mx);  
}
inline void pb (int p) { v[p].sb = v[p<<1].sb+v[p<<1|1].sb; }
void uadd (int p, ll k) {
    v[p].ad += k; v[p].sb += (v[p].r-v[p].l+1)*k; 
}
void usv (int p, ll k) {
    v[p].dx += k;
    v[p].sb += (v[p>>1].sa-v[p^1].sa)*k;
} 
void ads (int p, ll dm, ll dx) {
    // cout << p << " " << dm << " " << dx << " " << v[p].l << " " << v[p].r << " " << v[p].mx << endl; 
    if (v[p].l == v[p].r) return v[p].sb += max(dm, v[p].mx)*dx, void(); 
    if (dm > v[p<<1].mx) uadd(p<<1, dm*dx), ads(p<<1|1, dm, dx); 
    else ads(p<<1, dm, dx), usv(p<<1|1, dx); 
    pb(p); 
}
inline void push_down (int p) {
    if (v[p].ad) uadd(p<<1, v[p].ad), uadd(p<<1|1, v[p].ad), v[p].ad = 0; 
    if (!v[p].dx) return; 
    if (v[p^1].mx > v[p<<1].mx) uadd(p<<1, v[p^1].mx*v[p].dx), ads(p<<1|1, v[p^1].mx, v[p].dx); 
    else ads(p<<1, v[p^1].mx, v[p].dx), usv(p<<1|1, v[p].dx); 
    v[p].dx = 0; 
}
ll qsum (int p, int l, int r, int tl, int tr) {
    if (tl <= l && r <= tr) return v[p].sb; 
    int mid = l+r>>1; ll res = 0; push_down(p); 
    if (tl <= mid) res += qsum(p<<1, l, mid, tl, tr); 
    if (tr > mid) res += qsum(p<<1|1, mid+1, r, tl, tr); 
    return res; 
}
void add (int p, int l, int r, int tl, int tr, ll &mx) {
    if (tl <= l && r <= tr) return ads(p, mx, 1), mx = max(v[p].mx, mx), void(); 
    int mid = l+r>>1; push_down(p); 
    if (tl <= mid) add(p<<1, l, mid, tl, tr, mx); 
    if (tr > mid) add(p<<1|1, mid+1, r, tl, tr, mx); 
    pb(p); 
}
void mdy (int p, int l, int r, int id, int k) {
    if (l == r) return v[p].sa = v[p].mx = k, void(); 
    int mid = l+r>>1; push_down(p); 
    id <= mid ? mdy(p<<1, l, mid, id, k) : mdy(p<<1|1, mid+1, r, id, k); 
    pa(p); 
}
void build (int p, int l, int r) {
    v[p].l = l; v[p].r = r; 
    if (l == r) return v[p].sa = v[p].mx = a[l], void(); 
    int mid = l+r>>1; 
    build(p<<1, l, mid); build(p<<1|1, mid+1, r); 
    pa(p); 
}

int main () {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> n >> m; 
    for (int i = 1;i <= n;i++) cin >> a[i]; 
    build(1, 1, n); 
    while (m--) {
        int o, l, r; 
        cin >> o >> l >> r; 
        if (o == 1) mdy(1, 1, n, l, r); 
        if (o == 2) {
            ll mx = 0; 
            add(1, 1, n, l, r, mx); 
        }
        if (o == 3) cout << qsum(1, 1, n, l, r) << "\n"; 
    }
    return 0; 
}