#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using vll = __int128;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 1000010;
const ll inf = 1e18;

int n, m, a[maxn], lst[maxn], isq[maxn], mx[maxn], cur[maxn], vis[maxn];
vll ans[maxn];
ll val[maxn], lz[maxn << 2], lzmn[maxn << 2], lzc[maxn << 2];
vector<tuple<int, int, int>> vec[maxn];
vector<int> st[maxn], ed[maxn];
vector<pii> que[maxn];

struct node {
  vll hsum;
  ll sum, mn, smn, cntmn;
  friend node operator+(node x, node y) {
    node res;
    res.sum = x.sum + y.sum, res.hsum = x.hsum + y.hsum;
    res.mn = min(x.mn, y.mn), res.smn = inf;
    if (x.mn != res.mn) chkmn(res.smn, x.mn);
    if (x.smn != res.mn) chkmn(res.smn, x.smn);
    if (y.mn != res.mn) chkmn(res.smn, y.mn);
    if (y.smn != res.mn) chkmn(res.smn, y.smn);
    res.cntmn = 0;
    if (x.mn == res.mn) res.cntmn += x.cntmn;
    if (y.mn == res.mn) res.cntmn += y.cntmn;
    if (x.mn != res.mn) res.sum += x.mn * x.cntmn;
    if (y.mn != res.mn) res.sum += y.mn * y.cntmn;
    return res;
  }
} t[maxn << 2];

#define mid ((l + r) >> 1)

void build(int c, int l, int r) {
  if (l == r) {
    t[c].mn = 0, t[c].smn = 1e18;
    t[c].cntmn = 0;
    t[c].sum = t[c].hsum = 0;
    return;
  }
  build(c << 1, l, mid);
  build(c << 1 | 1, mid + 1, r);
  t[c] = t[c << 1] + t[c << 1 | 1];
}

void tagaddmn(int c, int l, int r, ll v) {
  t[c].hsum += (vll)t[c].cntmn * v, lzmn[c] += v;
}

void tagadd(int c, int l, int r, ll v) {
  t[c].hsum += (vll)t[c].sum * v, lz[c] += v;
}

void upd(int, int, int, int, int, ll);

void down(int c, int l, int r) {
  tagadd(c << 1, l, mid, lz[c]), tagadd(c << 1 | 1, mid + 1, r, lz[c]);
  if (t[c << 1].mn <= t[c << 1 | 1].mn) tagaddmn(c << 1, l, mid, lzmn[c]);
  else tagaddmn(c << 1, l, mid, lz[c] * t[c << 1].mn);
  if (t[c << 1 | 1].mn <= t[c << 1].mn) tagaddmn(c << 1 | 1, mid + 1, r, lzmn[c]);
  else tagaddmn(c << 1 | 1, mid + 1, r, lz[c] * t[c << 1 | 1].mn);
  lz[c] = lzmn[c] = 0;
  if (lzc[c] != 0) {
    upd(c << 1, l, mid, l, mid, lzc[c]);
    upd(c << 1 | 1, mid + 1, r, mid + 1, r, lzc[c]);
    lzc[c] = 0;
  }
}

void upd(int c, int l, int r, int x, int y, ll v) {
  if (l == x && r == y) {
    if (v <= t[c].mn) return;
    if (v >= t[c].smn) {
      down(c, l, r);
      upd(c << 1, l, mid, x, mid, v);
      upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
      return t[c] = t[c << 1] + t[c << 1 | 1], void();
    }
    chkmx(lzc[c], v), t[c].mn = v;
    return;
  }
  down(c, l, r);
  if (y <= mid) upd(c << 1, l, mid, x, y, v);
  else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v);
  else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v);
  t[c] = t[c << 1] + t[c << 1 | 1];
}

vll qry(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return t[c].hsum;
  down(c, l, r);
  if (y <= mid) return qry(c << 1, l, mid, x, y);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y);
  else return qry(c << 1, l, mid, x, mid) + qry(c << 1 | 1, mid + 1, r, mid + 1, y);
}

void flip(int c, int l, int r, int x) {
  if (l == r) return t[c].cntmn ^= 1, t[c].mn = t[c].sum = 0, void();
  down(c, l, r);
  if (x <= mid) flip(c << 1, l, mid, x);
  else flip(c << 1 |  1, mid + 1, r, x);
  t[c] = t[c << 1] + t[c << 1 | 1];
}

#undef mid

void print(vll x) {
  if (!x) return;
  print(x / 10), cout << int(x % 10);
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m;
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, m) {
    int op, x, y;
    cin >> op >> x >> y;
    if (op == 1) {
      vec[x].emplace_back(lst[x], i - 1, a[x]);
      a[x] = y, lst[x] = i;
    } else if (op == 2) {
      if (x > y) continue;
      st[x].emplace_back(i);
      ed[y + 1].emplace_back(i);
    } else {
      isq[i] = 1;
      if (x > y) continue;
      que[x - 1].emplace_back(i, -1);
      que[y].emplace_back(i, 1);
    }
  }
  rep (i, 1, n) vec[i].emplace_back(lst[i], m, a[i]);
  build(1, 0, m);
  rep (i, 1, n) {
    for (int x : st[i]) flip(1, 0, m, x);
    for (int x : ed[i]) flip(1, 0, m, x);
    for (auto [l, r, w] : vec[i]) {
      upd(1, 0, m, l, r, w);
    }
    tagaddmn(1, 0, m, t[1].mn), tagadd(1, 0, m, 1);
    for (auto [x, coe] : que[i]) {
      ans[x] += coe * qry(1, 0, m, 1, x);
    }
  }
  rep (i, 1, m) if (isq[i]) {
    if (ans[i]) print(ans[i]), cout << '\n';
    else cout << "0\n";
  }
}