#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 3e5 + 5;
struct ITBeats {
private:
vector<ll> sum, hi, secHi, cntHi, lazy;
public:
ITBeats (int sz) : sum(4 * sz), hi(4 * sz), secHi(4 * sz, LLONG_MIN),
cntHi(4 * sz, 1), lazy(4 * sz, LLONG_MIN) {}
private:
void apply (int k, int chmin) {
sum[k] -= (hi[k] - chmin) * cntHi[k];
lazy[k] = hi[k] = chmin;
}
void refine (int k) {
sum[k] = sum[k << 1] + sum[k << 1 | 1];
if (hi[k << 1] == hi[k << 1 | 1]) {
hi[k] = hi[k << 1], secHi[k] = max(secHi[k << 1], secHi[k << 1 | 1]);
cntHi[k] = cntHi[k << 1] + cntHi[k << 1 | 1];
}
else if (hi[k << 1] > hi[k << 1 | 1]) {
hi[k] = hi[k << 1], cntHi[k] = cntHi[k << 1];
secHi[k] = max(secHi[k << 1], hi[k << 1 | 1]);
}
else {
hi[k] = hi[k << 1 | 1], cntHi[k] = cntHi[k << 1 | 1];
secHi[k] = max(hi[k << 1], secHi[k << 1 | 1]);
}
}
void pushDown (int k, int l, int r) {
if (lazy[k] == LLONG_MIN) return;
if (lazy[k] < hi[k << 1]) apply(k << 1, lazy[k]);
if (lazy[k] < hi[k << 1 | 1]) apply(k << 1 | 1, lazy[k]);
lazy[k] = LLONG_MIN;
}
pl merging (pl a, pl b) {
if (a.first == b.first) return {a.first, max(a.second, b.second)};
if (a.first > b.first) return {a.first, max(a.second, b.first)};
if (a.first < b.first) return {b.first, max(a.first, b.second)};
}
public:
void update (int a, int b, int chmin, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a || chmin >= hi[k]) return;
if (a <= l && r <= b) {
if (secHi[k] < chmin && chmin < hi[k])
return apply(k, chmin), void();
}
pushDown(k, l, r);
int mid = (l + r) >> 1;
update(a, b, chmin, k << 1, l, mid);
update(a, b, chmin, k << 1 | 1, mid + 1, r);
refine(k);
}
void assgn (int pos, int val, int k = 1, int l = 1, int r = mn) {
if (pos < l || r < pos) return;
if (l == r)
return hi[k] = sum[k] = val, secHi[k] = LLONG_MIN, cntHi[k] = 1, void();
pushDown(k, l, r); int mid = (l + r) >> 1;
assgn(pos, val, k << 1, l, mid);
assgn(pos, val, k << 1 | 1, mid + 1, r);
refine(k);
}
ll query (int a, int b, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return sum[k];
pushDown(k, l, r); int mid = (l + r) >> 1;
return query(a, b, k << 1, l, mid) + query(a, b, k << 1 | 1, mid + 1, r);
}
int queryCnt (int a, int b, int hiCur, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return (hi[k] == hiCur ? cntHi[k] : 0);
pushDown(k, l, r); int mid = (l + r) >> 1;
return queryCnt(a, b, hiCur, k << 1, l, mid) +
queryCnt(a, b, hiCur, k << 1 | 1, mid + 1, r);
}
pl queryMax (int a, int b, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return make_pair(LLONG_MIN, LLONG_MIN);
if (a <= l && r <= b) return make_pair(hi[k], secHi[k]);
pushDown(k, l, r); int mid = (l + r) >> 1;
return merging(queryMax(a, b, k << 1, l, mid),
queryMax(a, b, k << 1 | 1, mid + 1, r));
}
int walking (int need, int hiCur, int k, int l, int r) {
if (l == r) {
int cntCur = (hi[k] == hiCur ? cntHi[k] : 0);
return (cntCur ? l : l - 1);
}
pushDown(k, l, r); int mid = (l + r) >> 1;
int cntLeft = (hi[k << 1] == hiCur ? cntHi[k << 1] : 0);
if (cntLeft >= need) return walking(need, hiCur, k << 1, l, mid);
return walking(need - cntLeft, hiCur, k << 1 | 1, mid + 1, r);
}
int walk (int a, int b, int need, int hiCur, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return r;
if (a <= l && r <= b) {
int curCnt = (hi[k] == hiCur ? cntHi[k] : 0);
return (curCnt >= need ? walking(need, hiCur, k, l, r) : r);
}
pushDown(k, l, r);
int mid = (l + r) >> 1, goLeft = walk(a, b, need, hiCur, k << 1, l, mid);
int cntLeft = queryCnt(a, b, hiCur, k << 1, l, mid);
return (goLeft == mid && mid < b && cntLeft < need ? walk(a, b, need - cntLeft, hiCur, k << 1 | 1, mid + 1, r) : goLeft);
}
} tree(mn);
void initialise (int _N, int _Q, int h[]) {
for (int i = 1; i <= _N; i++) tree.assgn(i, h[i]);
}
void cut (int l, int r, int k) {
int oldK = k;
while (k > 0) {
ll best, secBest; tie(best, secBest) = tree.queryMax(l, r);
secBest = max(0LL, secBest);
int cntHi = tree.queryCnt(l, r, best);
if (best == 0) return;
if ((best - secBest) * cntHi <= k) {
k -= (best - secBest) * cntHi;
tree.update(l, r, secBest);
}
else {
ll fully = k / cntHi, cur = best - fully;
k -= fully * cntHi, tree.update(l, r, cur);
if (k) {
int pos = tree.walk(l, r, k, cur);
tree.update(l, min(pos, r), cur - 1), k = 0;
}
}
}
}
void magic (int i, int x) {
tree.assgn(i, x);
}
ll inspect (int l, int r) {
return tree.query(l, r, 1);
}
#ifdef LOCAL
int init[mn];
int main()
{
freopen("WEIRD.inp", "r", stdin);
freopen("WEIRD.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> init[i];
initialise(n, q, init);
while (q--) {
int type; cin >> type;
if (type == 1) {
int l, r, k; cin >> l >> r >> k;
cut(l, r, k);
}
else if (type == 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
