#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct segment_tree_beat{
int N;
vector<int> mx, mx2, cnt_mx;
vector<ll> sum;
segment_tree_beat() : mx(), mx2(), cnt_mx(), sum() {}
segment_tree_beat(int n) : N(n), mx(n << 2), mx2(n << 2), cnt_mx(n << 2), sum(n << 2) {}
void pull(int id){
sum[id] = sum[id << 1] + sum[id << 1 | 1];
if(mx[id << 1] == mx[id << 1 | 1]){
mx[id] = mx[id << 1];
mx2[id] = max(mx2[id << 1], mx2[id << 1 | 1]);
cnt_mx[id] = cnt_mx[id << 1] + cnt_mx[id << 1 | 1];
} else if(mx[id << 1] > mx[id << 1 | 1]){
mx[id] = mx[id << 1];
mx2[id] = max(mx2[id << 1], mx[id << 1 | 1]);
cnt_mx[id] = cnt_mx[id << 1];
} else{
mx[id] = mx[id << 1 | 1];
mx2[id] = max(mx[id << 1], mx2[id << 1 | 1]);
cnt_mx[id] = cnt_mx[id << 1 | 1];
}
}
void chmin(int id, int l, int r, int val){
if(mx[id] <= val) return;
assert(mx2[id] < val);
sum[id] -= 1LL * (mx[id] - val) * cnt_mx[id];
mx[id] = val;
}
void down(int id, int l, int r, int mid){
chmin(id << 1, l, mid, mx[id]);
chmin(id << 1 | 1, mid + 1, r, mx[id]);
}
void build(int id, int l, int r, const vector<int>& A){
if(l == r){
mx[id] = A[l];
mx2[id] = -1;
cnt_mx[id] = 1;
sum[id] = A[l];
} else{
int mid = l + r >> 1;
build(id << 1, l, mid, A);
build(id << 1 | 1, mid + 1, r, A);
pull(id);
}
}
void change(int id, int l, int r, int pos, int val){
if(l == r){
mx[id] = val;
sum[id] = val;
} else{
int mid = l + r >> 1;
down(id, l, r, mid);
if(pos <= mid) change(id << 1, l, mid, pos, val);
else change(id << 1 | 1, mid + 1, r, pos, val);
pull(id);
}
}
void chmin(int id, int l, int r, int u, int v, int val){
if(v < l || u > r || mx[id] <= val) return;
if(u <= l && r <= v && mx2[id] < val) chmin(id, l, r, val);
else{
int mid = l + r >> 1;
chmin(id << 1, l, mid, u, v, val);
chmin(id << 1 | 1, mid + 1, r, u, v, val);
pull(id);
}
}
long long query(int id, int l, int r, int u, int v){
if(v < l || u > r) return 0;
if(u <= l && r <= v) return sum[id];
int mid = l + r >> 1;
down(id, l, r, mid);
return query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v);
}
int a, b, c;
void rec(int id, int l, int r, int u, int v){
if(u <= l && r <= v){
if(a == mx[id]){
c += cnt_mx[id];
b = max(b, mx2[id]);
} else if(a > mx[id]){
b = max(b, mx[id]);
} else{
b = max(mx2[id], a);
a = mx[id];
c = cnt_mx[id];
}
} else{
int mid = l + r >> 1;
down(id, l, r, mid);
if(u <= mid) rec(id << 1, l, mid, u, v);
if(mid < v) rec(id << 1 | 1, mid + 1, r, u, v);
}
}
tuple<int, int, int> get_info(int l, int r){
a = 0, b = 0, c = 0;
rec(1, 0, N - 1, l, r);
return make_tuple(a, b, c);
}
int walk(int id, int l, int r, int k){
if(l == r) return l;
int mid = l + r >> 1;
down(id, l, r, mid);
if(mx[id << 1] == mx[id << 1 | 1]){
if(k - cnt_mx[id << 1] > 0) return walk(id << 1 | 1, mid + 1, r, k - cnt_mx[id << 1]);
else return walk(id << 1, l, mid, k);
} else if(mx[id << 1] > mx[id << 1 | 1]){
return walk(id << 1, l, mid, k);
} else{
return walk(id << 1 | 1, mid + 1, r, k);
}
assert(false);
}
void search_info(int id, int l, int r, int u, int v, vector<tuple<int, int, int>>& info){
if(u <= l && r <= v){
info.emplace_back(id, l, r);
} else{
int mid = l + r >> 1;
down(id, l, r, mid);
if(u <= mid) search_info(id << 1, l, mid, u, v, info);
if(mid < v) search_info(id << 1 | 1, mid + 1, r, u, v, info);
}
}
int find_pos(int l, int r, int kth, int target){
vector<tuple<int, int, int>> info;
search_info(1, 0, N - 1, l, r, info);
for(auto [id, l, r] : info) if(mx[id] == target){
if(kth > cnt_mx[id]){
kth -= cnt_mx[id];
} else return walk(id, l, r, kth);
}
assert(false);
return -1;
}
};
int N;
vector<int> H;
segment_tree_beat tr;
void initialise(int _N, int Q, int _H[]){
N = _N;
H.resize(N);
for(int i = 0; i < N; ++i) H[i] = _H[i + 1];
tr = segment_tree_beat(N);
tr.build(1, 0, N - 1, H);
}
void cut(int l, int r, int k){
--l, --r;
long long tmp = tr.query(1, 0, N - 1, l, r);
// cout << "cur : " << l << ' ' << r << ' ' << tmp << '\n';
if(tmp <= k){
tr.chmin(1, 0, N - 1, l, r, 0);
// cout << '\n' << '\n';
return;
}
while(true){
int mx, mx2, cnt_mx;
tie(mx, mx2, cnt_mx) = tr.get_info(l, r);
// cout << mx2 << ' ' << mx << ' ' << cnt_mx << '\n';
assert(mx2 < mx);
long long t = 1LL * (mx - mx2) * cnt_mx;
if(t < k){
k -= t;
// cout << "manual : " << l << ' ' << r << ' ' << mx2 << '\n';
tr.chmin(1, 0, N - 1, l, r, mx2);
} else{
int dec = (k + cnt_mx - 1) / cnt_mx;
int mod = k % cnt_mx;
// cout << dec << ' ' << mod << '\n';
if(mod > 0){
int pos = tr.find_pos(l, r, mod, mx);
// cout << "half : " << l << ' ' << pos << ' ' << mx - pos << '\n';
tr.chmin(1, 0, N - 1, l, pos, mx - dec);
assert(pos < r);
// cout << "other : " << pos + 1 << ' ' << r << ' ' << mx - dec + 1 << '\n';
tr.chmin(1, 0, N - 1, pos + 1, r, mx - dec + 1);
} else{
// cout << "manual : " << l << ' ' << r << ' ' << mx - dec << '\n';
tr.chmin(1, 0, N - 1, l, r, mx - dec);
}
break;
}
}
// cout << '\n' << '\n';
}
void magic(int i, int x){
--i;
tr.change(1, 0, N - 1, i, x);
}
long long inspect(int l, int r){
--l, --r;
return tr.query(1, 0, N - 1, l, r);
}
#ifdef LOCAL
int main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int N, Q;
cin >> N >> Q;
int H[N + 1];
for(int i = 1; i <= N; ++i) cin >> H[i];
initialise(N, Q, H);
while(Q--){
int t;
cin >> t;
if(t == 1){
int l, r, k;
cin >> l >> r >> k;
cut(l, r, k);
} else if(t == 2){
int i, x;
cin >> i >> x;
magic(i, x);
} else{
int l, r;
cin >> l >> r;
cout << inspect(l, r) << '\n';
}
}
return 0;
}
#endif //LOCAL
