# include <bits/stdc++.h>

using namespace std;

constexpr long N(200'000);
constexpr long Q(200'000);

typedef pair<long, long> pair;

struct event {
  long op, v, l, r;
};

long n, q;
long a[N + 1];
long s[N + 1];
event e[Q + 1];

vector<long> id1;
long stk[Q], *top(stk);
vector<long> ins[N + 1];
set<long> set;
long cnt[Q + 1];
long prv[Q + 1];
long vl1[Q + 1];
long vl2[Q + 1];
long sum[Q + 1];

vector<::pair> upd[N + 1];
long ans[Q + 1];

inline long clc(long const i, long const x)
{ return e[prv[x]].v + i * (cnt[x] - cnt[prv[x]]); }

inline bool cmp(long const i, long const j, long const k) {
  long const vij(e[j].v - e[i].v), vjk(e[k].v - e[j].v);
  long const cij(cnt[j] - cnt[i]), cjk(cnt[k] - cnt[j]);
  assert(vij > 0), assert(vjk > 0);
  assert(cij > 0), assert(cjk > 0);
  return __int128_t(vij) * cjk >= __int128_t(vjk) * cij;
}

int main() {
  cin >> n >> q;
  for (long i(1); i <= n; ++i) cin >> a[i];
  partial_sum(a + 1, a + n + 1, s + 1);
  for (long i(1); i <= q; ++i) {
    switch (cin >> e[i].op, e[i].op) {
      case 1: cin >> e[i].v; break;
      case 2: break;
      case 3: cin >> e[i].l >> e[i].r; break;
    }
    if (e[i].op == 1) id1.push_back(i);
    cnt[i] = cnt[i - 1] + (e[i].op == 2);
    if (e[i].op == 3) {
      long const l(e[i].l - 1);
      long const r(e[i].r - 0);
      upd[l].emplace_back(i, +1);
      upd[r].emplace_back(i, -1);
      ans[i] += s[r] - s[l];
      ans[i] += (l + r + 1) * (r - l) / 2 * cnt[i];
    }
  }
  if (!id1.empty()) {
    for (long const i : id1) {
      if (top != stk && cnt[i] == cnt[top[-1]] && e[i].v > e[top[-1]].v)
        continue;
      while (top != stk && cnt[top[-1]] == cnt[i]) --top;
      while (top != stk && e[i].v <= e[top[-1]].v) --top;
      while (top - stk > 1 && cmp(top[-2], top[-1], i)) --top;
      if (top == stk) ins[1].push_back(i);
      else {
        long const dv(e[i].v - e[top[-1]].v);
        long const dc(cnt[i] - cnt[top[-1]]);
        ins[dv / dc + 1].push_back(i);
      }
      *top++ = i;
    }
    ::set.insert(0), ::set.insert(q + 1);
    for (long i(id1.front()); i <= q; ++i)
      prv[i] = id1.front();
    for (long i(1); i <= n; ++i) {
      for (long const j : ins[i]) {
        auto const k(::set.insert(j).first);
        auto const dv(e[j].v - e[*prev(k)].v);
        auto const dc(cnt[j] - cnt[*prev(k)]);
        for (long l(j); l != *next(k); ++l)
          prv[l] = j, vl1[l] += dv, vl2[l] += dc;
      }
      long l(-1), r(id1.size());
      while (r - l > 1) {
        long const m((l + r) / 2);
        (a[i] + i * cnt[id1.at(m)] < clc(i, id1.at(m)) ? l : r) = m;
      }
      long const p(r == long(id1.size()) ? q + 1 : id1.at(r));
      for (long j(p); j <= q; ++j) {
        // sum[j] += a[i] + i * cnt[prv[j]] - e[prv[j]].v;
        sum[j] += a[i] - vl1[j] + i * vl2[j];
      }
      for (auto const& j : upd[i]) ans[j.first] += j.second * sum[j.first];
    }
  }
  for (long i(1); i <= q; ++i)
    if (e[i].op == 3)
      cout << ans[i] << '\n';
}