# include <bits/stdc++.h>

using namespace std;

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

typedef pair<long, long> pair;

class segtree {
  constexpr static long L = __lg(N) + 1;
  struct node {
    // long sum[4];
    long tag[3];
    long add[3];
    /* tag[0] : sum[0] -> sum[3] *
     * tag[1] : sum[1] -> sum[3] *
     * tag[2] : sum[2] -> sum[3] *
     * add[1] : sum[0] -> sum[1] *
     * add[2] : sum[0] -> sum[2] */
    constexpr node() : /* sum{}, */ tag{}, add{} {}
    constexpr void app(long const* const tag, long const* const add) {
      // this->sum[3] += this->sum[0] * tag[0];
      // this->sum[3] += this->sum[1] * tag[1];
      // this->sum[3] += this->sum[2] * tag[2];
      // this->sum[1] += this->sum[0] * add[1];
      // this->sum[2] += this->sum[0] * add[2];
      this->tag[0] += this->add[1] * tag[1];
      this->tag[0] += this->add[2] * tag[2];
      this->tag[0] += tag[0];
      this->tag[1] += tag[1];
      this->tag[2] += tag[2];
      this->add[1] += add[1];
      this->add[2] += add[2];
    }
    constexpr void apptag(long const v0, long const v1, long const v2) {
      // sum[3] += sum[0] * v0;
      // sum[3] += sum[1] * v1;
      // sum[3] += sum[2] * v2;
      tag[0] += add[1] * v1;
      tag[0] += add[2] * v2;
      tag[0] += v0;
      tag[1] += v1;
      tag[2] += v2;
    }
    constexpr void appadd(long const v1, long const v2) {
      // sum[1] += sum[0] * v1;
      // sum[2] += sum[0] * v2;
      add[1] += v1;
      add[2] += v2;
    }
  } v[1 << (L + 1)];
  constexpr void dn(long const x) {
    v[x << 1 | 0].app(v[x].tag, v[x].add);
    v[x << 1 | 1].app(v[x].tag, v[x].add);
    memset(v[x].tag, 0, sizeof v[x].tag);
    memset(v[x].add, 0, sizeof v[x].add);
  }
  constexpr void up(long const x __attribute__((unused))) {
    // v[x].sum[0] = v[x << 1 | 0].sum[0] + v[x << 1 | 1].sum[0];
    // v[x].sum[1] = v[x << 1 | 0].sum[1] + v[x << 1 | 1].sum[1];
    // v[x].sum[2] = v[x << 1 | 0].sum[2] + v[x << 1 | 1].sum[2];
    // v[x].sum[3] = v[x << 1 | 0].sum[3] + v[x << 1 | 1].sum[3];
  }
  public:
  constexpr segtree() : v{} {
    // for (long i(1); i != 1 << (L + 1); ++i)
    // v[i].sum[0] = 1 << (L - __lg(i));
  }
  constexpr void add(long l, long r, long const v1, long const v2) {
    l = (l - 1) | 1 << L;
    r = (r + 1) | 1 << L;
    for (long i(L); i; --i) dn(l >> i), dn(r >> i);
    while ((l ^ r) >> 1) {
      if ((l & 1) == 0) v[l ^ 1].appadd(v1, v2);
      if ((r & 1) == 1) v[r ^ 1].appadd(v1, v2);
      up(l >>= 1), up(r >>= 1);
    }
    while (l >>= 1) up(l);
    while (r >>= 1) up(r);
  }
  constexpr void tag(long l, long r, long v0, long v1, long v2) {
    l = (l - 1) | 1 << L;
    r = (r + 1) | 1 << L;
    for (long i(L); i; --i) dn(l >> i), dn(r >> i);
    while ((l ^ r) >> 1) {
      if ((l & 1) == 0) v[l ^ 1].apptag(v0, v1, v2);
      if ((r & 1) == 1) v[r ^ 1].apptag(v0, v1, v2);
      up(l >>= 1), up(r >>= 1);
    }
    while (l >>= 1) up(l);
    while (r >>= 1) up(r);
  }
  constexpr auto at(long x) {
    x |= 1 << L;
    for (long i(L); i; --i) dn(x >> i);
    return make_tuple(v[x].add[1], v[x].add[2], v[x].tag[0]);
  }
};

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];
segtree seg;

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

// inline long clc(long const i, long const x)
// { return vl1[x] + i * (cnt[x] - vl2[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)]);
        seg.add(j, *next(k) - 1, dv, dc);
        // 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);
        auto const info(seg.at(id1.at(m)));
        (a[i] < get<0>(info) - i * get<1>(info) ? l : r) = m;
      }
      long const p(r == long(id1.size()) ? q + 1 : id1.at(r));
      seg.tag(p, q, a[i], -1, i);
      // 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 * get<2>(seg.at(j.first));
    }
  }
  for (long i(1); i <= q; ++i)
    if (e[i].op == 3)
      cout << ans[i] << '\n';
}