#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 200005
int n, m, a[N], cnt[N];
struct op {int op, a, b; ll v;} p[N];
vector<int> ins[N];
namespace Lseg {
  struct Line {
    int k; ll b;
    il ll F(ll x) {return k * x + b;}
  } T[N];
  int rt, cnt, ls[N], rs[N];
  il void clr() {FOR(i, 1, cnt) ls[i] = rs[i] = 0; rt = 0;}
  il void insert(int &i, Line v, int l = 1, int r = n) {
    if(!i) {T[i = ++cnt] = v; return ;} int mid = l + r >> 1;
    if(T[i].F(mid) > v.F(mid)) swap(T[i], v);
    if(T[i].F(l) > v.F(l)) insert(ls[i], v, l, mid);
    if(T[i].F(r) > v.F(r)) insert(rs[i], v, mid + 1, r);
  }
  il void ins(int k, ll b) {insert(rt, {k, b});}
  il ll query(int i, int p, int l = 1, int r = n) {
    if(!i) return 1e18; ll s = T[i].F(p);
    if(l == r) return s; int mid = l + r >> 1;
    if(mid >= p) s = min(s, query(ls[i], p, l, mid));
    else s = min(s, query(rs[i], p, mid + 1, r)); return s;
  }
  il ll qry(int p) {return query(rt, p);}
}
/*
a[i] + i * cnt[j] >= v[j]
v[j] - i * cnt[j] <= a[i]
*/
il void solve(int l, int r, vector<int> &q) {
  if(q.empty()) return ;
  if(l == r) {for(auto x : q) ins[r].eb(x); return ;}
  int mid = l + r >> 1; vector<int> Lq, Rq;
  Lseg::clr(); FOR(i, l, mid) if(p[i].op == 1) Lseg::ins(-cnt[i], p[i].v);
  for(auto x : q) if(Lseg::qry(x) <= a[x]) Lq.eb(x); else Rq.eb(x);
  solve(l, mid, Lq), solve(mid + 1, r, Rq);
}
struct segt {
  ll s[N * 4], is[N * 4];
  int cnt[N * 4], tag[N * 4], mxr[N * 4];
  ll mx[N * 4]; int md[N * 4];
  il void build(int i = 1, int l = 1, int r = n) {
    md[i] = -1; if(l == r) return ;
    int mid = l + r >> 1; build(LS), build(RS);
  }
  il void pushup(int i) {
    int L = i << 1, R = L | 1;
    s[i] = s[L] + s[R], is[i] = is[L] + is[R], cnt[i] = cnt[L] + cnt[R];
    mxr[i] = max(mxr[L], mxr[R]), mx[i] = max(mx[L], mx[R]);
  }
  il void mpu(int i, int v) {
    s[i] = 1ll * cnt[i] * v, mx[i] = md[i] = v;
  }
  il void push(int i, int v) {
    s[i] += is[i] * v, tag[i] += v;
    mx[i] += 1ll * mxr[i] * v;
  }
  il void pushdown(int i) {
    int L = i << 1, R = L | 1;
    if(~md[i]) mpu(L, md[i]), mpu(R, md[i]), md[i] = -1;
    if(tag[i]) push(L, tag[i]), push(R, tag[i]), tag[i] = 0;
  }
  il void upd(int x, int v, int i = 1, int l = 1, int r = n) {
    if(l == r) {
      if(~v) mx[i] = s[i] = v, mxr[i] = is[i] = x, cnt[i] = 1;
      else mx[i] = s[i] = mxr[i] = is[i] = cnt[i] = 0; return ;
    }
    int mid = l + r >> 1; pushdown(i);
    if(mid >= x) upd(x, v, LS); else upd(x, v, RS); pushup(i);
  }
  il ll query(int el, int er, int i = 1, int l = 1, int r = n) {
    if(l >= el && r <= er) return s[i]; int mid = l + r >> 1; pushdown(i); ll ns = 0;
    if(mid >= el) ns += query(el, er, LS); if(mid < er) ns += query(el, er, RS); return ns;
  }
  il int binary(int el, int er, ll v, int i = 1, int l = 1, int r = n) {
    if(!cnt[i]) return -1; if(l >= el && r <= er) {if(mx[i] < v) return -1; if(l == r) return r;}
    int mid = l + r >> 1, ns = -1; pushdown(i); if(mid >= el) ns = binary(el, er, v, LS);
    if(~ns) return ns; if(mid < er) ns = binary(el, er, v, RS); return ns;
  }
  il void mdf(int el, int er, ll v, int i = 1, int l = 1, int r = n) {
    if(!cnt[i]) return ; if(l >= el && r <= er) return mpu(i, v); int mid = l + r >> 1; pushdown(i);
    if(mid >= el) mdf(el, er, v, LS); if(mid < er) mdf(el, er, v, RS); pushup(i);
  }
  il void op() {push(1, 1);}
  il void odt(int l, int r, ll v) {int k = binary(l, r, v); if(~k) mdf(k, r, v);}
  il void print(int i = 1, int l = 1, int r = n) {
    if(l == r) return ;
    if(l == r) {cout << s[i] << " \n"[r == n]; return ;}
    int mid = l + r >> 1; pushdown(i);
    print(LS), print(RS);
  }
} s, t;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  FOR(i, 1, n) cin >> a[i];
  vector<pii> pos; int tot = 0;
  FOR(i, 1, m) {
    auto &[op, a, b, v] = p[i];
    cin >> op;
    if(op == 1) cin >> v;
    if(op == 2) ++tot;
    if(op == 3) cin >> a >> b;
    cnt[i] = tot;
  }
  vector<int> q;
  FOR(i, 1, n) q.eb(i);
  solve(1, m + 1, q);
  s.build(), t.build();
  FOR(i, 1, n) s.upd(i, a[i]);
  FOR(i, 1, m) {
    auto [op, a, b, v] = p[i];
    for(auto x : ins[i]) s.upd(x, -1), t.upd(x, v);
    // for(auto x : ins[i]) cerr << x << " " << i << "\n";
    if(op == 1) t.odt(1, n, v); if(op == 2) s.op(), t.op();
    if(op == 3) cerr << i << "\n", cout << s.query(a, b) + t.query(a, b) << "\n";
    // if(i == 5) t.print();
    // if(i == 6) t.print();
    t.print();
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}