# include <bits/stdc++.h>

using namespace std;

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

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 cnt[Q + 1];
long prv[Q + 1];
long sum[Q + 1];

vector<pair<long, long>> 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]]); }

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 i(id1.front()); i <= q; ++i)
      prv[i] = id1.front();
    for (long i(1); i <= n; ++i) {
      // cerr << "clc" << ' ' << i << '\n';
      for (long const j : id1) if (clc(i, j) > e[j].v) {
        // cerr << "ins" << ' ' << j << '\n';
        for (long k(j); k <= q && prv[k] < j; ++k) prv[k] = j;
      }
      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));
      // cerr << "partition" << ' ' << p << '\n';
      for (long j(p); j <= q; ++j)
        sum[j] += a[i] + i * cnt[prv[j]] - e[prv[j]].v;
      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';
}