#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char ch = getchar();
  long long nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  long long ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
void print(vector<long long> x) {
  for (long long i = 0; i < (long long)x.size(); i++)
    printf("%lld%c", x[i], " \n"[i == (long long)x.size() - 1]);
}
long long n, Q;
struct SMT {
  long long t[200005 * 4], tag[200005 * 4];
  void upd(long long u, long long l, long long r, long long v) {
    tag[u] += v, t[u] += v * (r - l + 1);
  }
  void pushdown(long long u, long long l, long long r) {
    upd((u << 1), l, ((l + r) / 2), tag[u]),
        upd((u << 1 | 1), ((l + r) / 2) + 1, r, tag[u]), tag[u] = 0;
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v) {
    if (L > R) return;
    if (L <= l && r <= R) return upd(u, l, r, v);
    pushdown(u, l, r);
    if (((l + r) / 2) >= L) update((u << 1), l, ((l + r) / 2), L, R, v);
    if (((l + r) / 2) < R) update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v);
    t[u] = t[(u << 1)] + t[(u << 1 | 1)];
  }
  long long query(long long u, long long l, long long r, long long L,
                  long long R) {
    if (L <= l && r <= R) return t[u];
    pushdown(u, l, r);
    long long ans = 0;
    if (((l + r) / 2) >= L) ans += query((u << 1), l, ((l + r) / 2), L, R);
    if (((l + r) / 2) < R)
      ans += query((u << 1 | 1), ((l + r) / 2) + 1, r, L, R);
    return ans;
  }
} smt;
struct Driver {
  long long mx[200005 * 4], second[200005 * 4], cnt[200005 * 4],
      tag[200005 * 4];
  void pushup(long long u) {
    if (mx[(u << 1)] == mx[(u << 1 | 1)]) {
      mx[u] = mx[(u << 1)],
      second[u] = max(second[(u << 1)], second[(u << 1 | 1)]);
      cnt[u] = cnt[(u << 1)] + cnt[(u << 1 | 1)];
    } else if (mx[(u << 1)] > mx[(u << 1 | 1)]) {
      mx[u] = mx[(u << 1)], second[u] = max(mx[(u << 1 | 1)], second[(u << 1)]);
      cnt[u] = cnt[(u << 1)];
    } else {
      mx[u] = mx[(u << 1 | 1)],
      second[u] = max(mx[(u << 1)], second[(u << 1 | 1)]);
      cnt[u] = cnt[(u << 1 | 1)];
    }
  }
  void upd(long long u, long long v) {
    if (v < mx[u]) mx[u] = v, tag[u] = v;
  }
  void pushdown(long long u) {
    if (tag[u] == 0x3f3f3f3f) return;
    upd((u << 1), tag[u]), upd((u << 1 | 1), tag[u]);
    tag[u] = 0x3f3f3f3f;
  }
  void build(long long u, long long l, long long r) {
    tag[u] = 0x3f3f3f3f;
    if (l == r) {
      mx[u] = l, cnt[u] = 1;
      return;
    }
    build((u << 1), l, ((l + r) / 2)),
        build((u << 1 | 1), ((l + r) / 2) + 1, r);
    pushup(u);
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v) {
    if (L > R || v >= mx[u]) return;
    if (L <= l && r <= R && v > second[u]) {
      smt.update(1, 1, n, v + 1, mx[u], -cnt[u]);
      upd(u, v);
      return;
    }
    pushdown(u);
    if (((l + r) / 2) >= L) update((u << 1), l, ((l + r) / 2), L, R, v);
    if (((l + r) / 2) < R) update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v);
    pushup(u);
  }
  void fix(long long u, long long l, long long r, long long pos, long long v) {
    if (l == r) {
      if (v > mx[u])
        smt.update(1, 1, n, mx[u] + 1, v, 1);
      else
        smt.update(1, 1, n, v + 1, mx[u], -1);
      mx[u] = v;
      return;
    }
    pushdown(u);
    if (pos <= ((l + r) / 2))
      fix((u << 1), l, ((l + r) / 2), pos, v);
    else
      fix((u << 1 | 1), ((l + r) / 2) + 1, r, pos, v);
    pushup(u);
  }
} smt2;
signed main() {
  cin >> n >> Q;
  smt2.build(1, 1, n);
  smt.update(1, 1, n, 1, n, 1);
  while (Q--) {
    long long op = read();
    if (op == 1) {
      long long p = read(), v = read();
      smt2.fix(1, 1, n, p, v);
      smt2.update(1, 1, n, 1, p - 1, p - 1);
    } else {
      long long l = read(), r = read();
      printf("%lld\n", smt.query(1, 1, n, l, r));
    }
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

There are n cities in a row numbered from 1 to n.

The cities will be building broadcasting stations. The station in the i-th city has height h_i and range w_i. It can broadcast information to city j if the following constraints are met: 

  * i ≤ j ≤ w_i, and 
  * for each k such that i < k ≤ j, the following condition holds: h_k < h_i. 

In other words, the station in city i can broadcast information to city j if j ≥ i, j is in the range of i-th station, and i is strictly highest on the range from i to j (including city j).

At the beginning, for every city i, h_i = 0 and w_i = i.

Then q events will take place. During i-th event one of the following will happen: 

  * City c_i will rebuild its station so that its height will be strictly highest among all stations and w_{c_i} will be set to g_i. 
  * Let b_j be the number of stations that can broadcast information to city j. Print the sum of b_j over all j satisfying l_i ≤ j ≤ r_i. 



Your task is to react to all events and print answers to all queries.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2⋅10^5) — number of cities and number of events.

Then q lines follow. The i-th line begins with an integer p_i (p_i = 1 or p_i = 2).

If p_i = 1 a station will be rebuilt. Then two integers c_i and g_i (1 ≤ c_i ≤ g_i ≤ n) follow — the city in which the station is rebuilt and its new broadcasting range.

If p_i = 2 you are given a query. Then two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) follow — the range of cities in the query.

Output

For each query, print in a single line the sum of b_j over the given interval.

Examples

Input


1 3
2 1 1
1 1 1
2 1 1


Output


1
1


Input


5 10
1 3 4
2 3 5
1 1 5
2 1 5
1 4 5
2 2 4
1 2 3
2 1 3
1 5 5
2 2 5


Output


4
10
5
4
5

Note

In the first test case, only station 1 reaches city 1 before and after it is rebuilt.

In the second test case, after each rebuild, the array b looks as follows: 

  1. [1, 1, 1, 2, 1]; 
  2. [1, 2, 2, 3, 2]; 
  3. [1, 2, 2, 1, 2]; 
  4. [1, 1, 2, 1, 2]; 
  5. [1, 1, 2, 1, 1]. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char ch = getchar();
  long long nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  long long ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
void print(vector<long long> x) {
  for (long long i = 0; i < (long long)x.size(); i++)
    printf("%lld%c", x[i], " \n"[i == (long long)x.size() - 1]);
}
long long n, Q;
struct SMT {
  long long t[200005 * 4], tag[200005 * 4];
  void upd(long long u, long long l, long long r, long long v) {
    tag[u] += v, t[u] += v * (r - l + 1);
  }
  void pushdown(long long u, long long l, long long r) {
    upd((u << 1), l, ((l + r) / 2), tag[u]),
        upd((u << 1 | 1), ((l + r) / 2) + 1, r, tag[u]), tag[u] = 0;
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v) {
    if (L > R) return;
    if (L <= l && r <= R) return upd(u, l, r, v);
    pushdown(u, l, r);
    if (((l + r) / 2) >= L) update((u << 1), l, ((l + r) / 2), L, R, v);
    if (((l + r) / 2) < R) update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v);
    t[u] = t[(u << 1)] + t[(u << 1 | 1)];
  }
  long long query(long long u, long long l, long long r, long long L,
                  long long R) {
    if (L <= l && r <= R) return t[u];
    pushdown(u, l, r);
    long long ans = 0;
    if (((l + r) / 2) >= L) ans += query((u << 1), l, ((l + r) / 2), L, R);
    if (((l + r) / 2) < R)
      ans += query((u << 1 | 1), ((l + r) / 2) + 1, r, L, R);
    return ans;
  }
} smt;
struct Driver {
  long long mx[200005 * 4], second[200005 * 4], cnt[200005 * 4],
      tag[200005 * 4];
  void pushup(long long u) {
    if (mx[(u << 1)] == mx[(u << 1 | 1)]) {
      mx[u] = mx[(u << 1)],
      second[u] = max(second[(u << 1)], second[(u << 1 | 1)]);
      cnt[u] = cnt[(u << 1)] + cnt[(u << 1 | 1)];
    } else if (mx[(u << 1)] > mx[(u << 1 | 1)]) {
      mx[u] = mx[(u << 1)], second[u] = max(mx[(u << 1 | 1)], second[(u << 1)]);
      cnt[u] = cnt[(u << 1)];
    } else {
      mx[u] = mx[(u << 1 | 1)],
      second[u] = max(mx[(u << 1)], second[(u << 1 | 1)]);
      cnt[u] = cnt[(u << 1 | 1)];
    }
  }
  void upd(long long u, long long v) {
    if (v < mx[u]) mx[u] = v, tag[u] = v;
  }
  void pushdown(long long u) {
    if (tag[u] == 0x3f3f3f3f) return;
    upd((u << 1), tag[u]), upd((u << 1 | 1), tag[u]);
    tag[u] = 0x3f3f3f3f;
  }
  void build(long long u, long long l, long long r) {
    tag[u] = 0x3f3f3f3f;
    if (l == r) {
      mx[u] = l, cnt[u] = 1;
      return;
    }
    build((u << 1), l, ((l + r) / 2)),
        build((u << 1 | 1), ((l + r) / 2) + 1, r);
    pushup(u);
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v) {
    if (L > R || v >= mx[u]) return;
    if (L <= l && r <= R && v > second[u]) {
      smt.update(1, 1, n, v + 1, mx[u], -cnt[u]);
      upd(u, v);
      return;
    }
    pushdown(u);
    if (((l + r) / 2) >= L) update((u << 1), l, ((l + r) / 2), L, R, v);
    if (((l + r) / 2) < R) update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v);
    pushup(u);
  }
  void fix(long long u, long long l, long long r, long long pos, long long v) {
    if (l == r) {
      if (v > mx[u])
        smt.update(1, 1, n, mx[u] + 1, v, 1);
      else
        smt.update(1, 1, n, v + 1, mx[u], -1);
      mx[u] = v;
      return;
    }
    pushdown(u);
    if (pos <= ((l + r) / 2))
      fix((u << 1), l, ((l + r) / 2), pos, v);
    else
      fix((u << 1 | 1), ((l + r) / 2) + 1, r, pos, v);
    pushup(u);
  }
} smt2;
signed main() {
  cin >> n >> Q;
  smt2.build(1, 1, n);
  smt.update(1, 1, n, 1, n, 1);
  while (Q--) {
    long long op = read();
    if (op == 1) {
      long long p = read(), v = read();
      smt2.fix(1, 1, n, p, v);
      smt2.update(1, 1, n, 1, p - 1, p - 1);
    } else {
      long long l = read(), r = read();
      printf("%lld\n", smt.query(1, 1, n, l, r));
    }
  }
  return 0;
}

```