#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef array<ll,2> pr;
const int MAXN = 2e5+10;

int n,q; ll a[MAXN];
int o[MAXN]; ll x[MAXN],y[MAXN];
pr arr[MAXN]; int rk[MAXN],num;
vector<int> mdf[MAXN];

namespace T{ //求出每个位置从何时开始被影响到
    void solve(){
        for(int i=1,cnt=0;i<=q;i++){
            if(o[i] == 2)cnt++;
            else if(o[i] == 1)arr[++num] = (pr){x[i],cnt},rk[num] = i;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=num;j++){
                ll d = i*arr[j][1] + a[i] - arr[j][0];
                if(d > 0){
                    mdf[rk[j]].push_back(i);
                    break;
                }
            }
        }
    }
}

int vis[MAXN]; ll va[MAXN],vb[MAXN];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++){
        cin>>o[i];
        if(o[i] == 1){
            cin>>x[i];
        }else if(o[i] == 3){
            cin>>x[i]>>y[i];
        }
    }
    T::solve();

    for(int i=1;i<=q;i++){
        if(o[i] == 1){
            for(int j=n;j>=1;j--)if(vis[j]){
                if(va[j] > x[i])va[j] = x[i];
                else break;
            }
            for(auto j : mdf[i]){
                vis[j] = 1; va[j] = x[i]; 
            }
        }else if(o[i] == 2){
            for(int j=1;j<=n;j++)vis[j] ? va[j]+=j : vb[j]+=j;
        }else{
            ll sum = 0;
            for(int j=x[i];j<=y[i];j++)sum += (vis[j] ? va[j] : vb[j]);
            cout<<sum<<"\n";
        }
    }

    return 0;
}