#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 1e5 + 10;

int n, q;

int last[N], a[N], L[N], R[N], t[N], x[N], y[N], idx[N];

vector<int> query[N], event[N];

struct IT {
  long long T[N << 2], _T[N << 2], cnt[N << 2], cntw[N << 2];
  long long lazy[2][N << 2];
  pair<long long, long long> mx[N << 2];
  void push(int s, int l, int r) {
    if (lazy[0][s] != -1) {
      T[s] = lazy[0][s] * cnt[s];
      mx[s].first = lazy[0][s];
      if (l != r) {
        lazy[0][s << 1] = lazy[0][s << 1 | 1] = lazy[0][s];
        lazy[1][s << 1] = lazy[1][s << 1 | 1] = 0;
      }
    }
    if (lazy[1][s]) {
      T[s] += lazy[1][s] * cntw[s];
      mx[s].first += mx[s].second * lazy[1][s];
      if (l != r) {
        lazy[1][s << 1] += lazy[1][s];
        lazy[1][s << 1 | 1] += lazy[1][s];
      }
    }
    lazy[0][s] = -1;
    lazy[1][s] = 0;
  }

  void Set (int s, int l, int r, int pos, long long val) {
    push(s, l, r);
    if (l == r) {
      if (val < 0) {
        T[s] = cnt[s] = cntw[s] = 0;
        mx[s] = make_pair(0, 0);
      }
      else {
        T[s] = val;
        cnt[s] = 1;
        cntw[s] = pos;
        mx[s] = make_pair(val, pos);
      }
      return;
    }
    int mid = l + r >> 1;
    if (pos <= mid) Set(s << 1, l, mid, pos, val);
    else Set(s << 1 | 1, mid + 1, r, pos, val);
    push(s << 1, l, mid);
    push(s << 1 | 1, mid + 1, r);
    T[s] = T[s << 1] + T[s << 1 | 1];
    cnt[s] = cnt[s << 1] + cnt[s << 1 | 1];
    cntw[s] = cntw[s << 1] + cntw[s << 1 | 1];
    mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
  }

  void up(int s, int l, int r, int from, int to, bool t, long long val) {
    push(s, l, r);
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      lazy[t][s] = val;
      push(s, l, r);
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, t, val);
    up(s << 1 | 1, mid + 1, r, from, to, t, val);
    T[s] = T[s << 1] + T[s << 1 | 1];
    mx[s] = max(mx[s << 1], mx[s << 1 | 1]);
  }

  long long get(int s, int l, int r, int from, int to) {
    push(s, l, r);
    if (l > to || r < from) return 0;
    if (from <= l && r <= to) return T[s];
    int mid = l + r >> 1;
    return get(s << 1, l, mid, from, to) + get(s << 1 | 1, mid + 1, r, from, to);
  }

  int Find (long long val) {
    int s = 1, l = 1, r = n;
    while (l != r) {
      push(s, l, r);
      int mid = l + r >> 1;
      push(s << 1, l, mid);
//      if (val == 7) cout << l << " " << r << " " << T[s << 1] << endl;
      if (mx[s << 1].first <= val) {
        s = s << 1 | 1;
        l = mid + 1;
      }
      else {
        s = s << 1;
        r = mid;
      }
    }
    push(s, l, r);
    return mx[s].first <= val ? l + 1 : l;
  }
} it1, it2;

struct line {
  long long m, c;
  long long eval (long long x) {
    return m * x + c;
  }
  float cut (line l) {
    return (float) (c - l.c) / (l.m - m);
  }
};

struct CHT {
  vector<line> st;
  void add (line cur) {
    if (!st.empty() && st.back().m == cur.m) {
      if (st.back().c <= cur.c) return;
      st.pop_back();
    }
    while (st.size() >= 2 && st.back().cut(cur) >= st.back().cut(st.end()[-2])) st.pop_back();
    st.push_back(cur);
  }
  long long query(long long x) {
    int l = 0, r = st.size() - 1;
    while (l < r) {
      int mid = l + r >> 1;
      if (st[mid].eval(x) <= st[mid + 1].eval(x)) r = mid;
      else l = mid + 1;
    }
    return st[l].eval(x);
  }
} cht;

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> q;

  for(int i = 1; i <= n; i++) cin >> a[i];

  int c = 0;
  vector<line> arr;
  for(int i = 1; i <= q; i++) {
    cin >> t[i];
    if (t[i] == 1) cin >> x[i];
    if (t[i] == 3) cin >> x[i] >> y[i];

    if (t[i] == 2) c++;
    if (t[i] == 1) {
      idx[arr.size()] = i;
      arr.push_back({c, x[i]});
    }
  }

  for(int i = 1; i <= n; i++) {
    L[i] = 0, R[i] = arr.size() - 1;
    last[i] = -1;
  }

  for(int loop = 1; loop <= 20; loop++) {
    bool stop = 1;
    for(int i = 1; i <= n; i++) if (L[i] <= R[i]) {
      stop = 0;
      query[L[i] + R[i] >> 1].push_back(i);
    }
    if (stop) break;
    for(int i = 0; i < arr.size(); i++) {
      cht.add(arr[i]);
      for(auto &j : query[i]) {
        long long val = cht.query(-j);
        if (val < a[j]) {
          last[j] = i;
          R[j] = i - 1;
        } else L[j] = i + 1;
      } query[i].clear();
    }
    cht.st.clear();
  }

  for(int i = 1; i <= n; i++) {
//    cout << last[i] << " ";
    if (last[i] >= 0) event[idx[last[i]]].push_back(i);
  }
//  cout << endl;

  for(int i = 1; i <= 4 * n; i++) {
    it1.lazy[0][i] = it2.lazy[0][i] = -1;
  }

  for(int i = 1; i <= n; i++) it1.Set(1, 1, n, i, a[i]);

  for(int i = 1; i <= q; i++) {
    if (t[i] == 1) {
      for(auto &j : event[i]) {
        it1.Set(1, 1, n, j, -1);
        it2.Set(1, 1, n, j, x[i]);
      }
      int start = it2.Find(x[i]);
      it2.up(1, 1, n, start, n, 0, x[i]);
    }
    if (t[i] == 2) {
      it1.up(1, 1, n, 1, n, 1, 1LL);
      it2.up(1, 1, n, 1, n, 1, 1LL);
    }
    if (t[i] == 3) {
      long long sum1 = it1.get(1, 1, n, x[i], y[i]);
      long long sum2 = it2.get(1, 1, n, x[i], y[i]);
      cout << sum1 + sum2 << endl;
    }
  }
}