#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
template <typename T>
inline void read(T &WOW) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  WOW = flag * x;
}
int n, q;
struct BIT {
  long long t1[MAXN], t2[MAXN];
  inline void add(int x, int v) {
    long long tmp = x * v;
    for (int i = x; i <= n; i += (i & (-i))) {
      t1[i] += v;
      t2[i] += tmp;
    }
  }
  inline long long sum(int x) {
    long long r1 = 0, r2 = 0;
    for (int i = x; i; i -= (i & (-i))) {
      r1 += t1[i];
      r2 += t2[i];
    }
    return r1 * (x + 1) - r2;
  }
  inline void upd(int l, int r, int v) {
    add(l, v);
    if (r < n) add(r + 1, -v);
  }
  inline long long qry(int l, int r) { return sum(r) - sum(l - 1); }
} seg1;
struct SegmentTreeBeats {
  int mx[MAXN << 2], mx2[MAXN << 2], cnt[MAXN << 2], tag[MAXN << 2];
  inline void puttag(int rt, int tg) { mx[rt] = tag[rt] = tg; }
  inline void pushdown(int rt) {
    if (tag[rt]) {
      int tmp = max(mx[(rt << 1)], mx[(rt << 1) | 1]);
      if (mx[(rt << 1)] == tmp) {
        puttag((rt << 1), tag[rt]);
      }
      if (mx[(rt << 1) | 1] == tmp) {
        puttag((rt << 1) | 1, tag[rt]);
      }
      tag[rt] = 0;
    }
  }
  inline void pushup(int rt) {
    if (mx[(rt << 1)] == mx[(rt << 1) | 1]) {
      mx[rt] = mx[(rt << 1)];
      mx2[rt] = max(mx2[(rt << 1)], mx2[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1)] + cnt[(rt << 1) | 1];
    } else if (mx[(rt << 1)] > mx[(rt << 1) | 1]) {
      mx[rt] = mx[(rt << 1)];
      mx2[rt] = max(mx2[(rt << 1)], mx[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1)];
    } else {
      mx[rt] = mx[(rt << 1) | 1];
      mx2[rt] = max(mx[(rt << 1)], mx2[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1) | 1];
    }
  }
  void Build(int rt, int b, int e) {
    if (b == e) {
      mx[rt] = b;
      mx2[rt] = 0;
      cnt[rt] = 1;
      return;
    }
    int mid = (b + e) >> 1;
    Build((rt << 1), b, mid);
    Build((rt << 1) | 1, mid + 1, e);
    pushup(rt);
  }
  void Insert(int rt, int b, int e, int p, int v) {
    if (b == e) {
      seg1.upd(b, mx[rt], -1);
      mx[rt] = v;
      seg1.upd(b, mx[rt], 1);
      return;
    }
    int mid = (b + e) >> 1;
    pushdown(rt);
    if (p <= mid)
      Insert((rt << 1), b, mid, p, v);
    else
      Insert((rt << 1) | 1, mid + 1, e, p, v);
    pushup(rt);
  }
  void UpdateMin(int rt, int b, int e, int l, int r, int v) {
    if (mx[rt] <= v) return;
    if (l <= b && e <= r && v > mx2[rt]) {
      seg1.upd(v + 1, mx[rt], -cnt[rt]);
      puttag(rt, v);
      return;
    }
    int mid = (b + e) >> 1;
    pushdown(rt);
    if (l <= mid) UpdateMin((rt << 1), b, mid, l, r, v);
    if (r > mid) UpdateMin((rt << 1) | 1, mid + 1, e, l, r, v);
    pushup(rt);
  }
} seg2;
void solve() {
  read(n);
  read(q);
  seg1.upd(1, n, 1);
  seg2.Build(1, 1, n);
  int type, l, r;
  while (q--) {
    read(type);
    read(l);
    read(r);
    if (type == 1) {
      seg2.Insert(1, 1, n, l, r);
      if (l > 1) seg2.UpdateMin(1, 1, n, 1, l - 1, l - 1);
    } else {
      printf("%lld\n", seg1.qry(l, r));
    }
  }
}
int main() {
  solve();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
const int MAXN = 200005;
template <typename T>
inline void read(T &WOW) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  WOW = flag * x;
}
int n, q;
struct BIT {
  long long t1[MAXN], t2[MAXN];
  inline void add(int x, int v) {
    long long tmp = x * v;
    for (int i = x; i <= n; i += (i & (-i))) {
      t1[i] += v;
      t2[i] += tmp;
    }
  }
  inline long long sum(int x) {
    long long r1 = 0, r2 = 0;
    for (int i = x; i; i -= (i & (-i))) {
      r1 += t1[i];
      r2 += t2[i];
    }
    return r1 * (x + 1) - r2;
  }
  inline void upd(int l, int r, int v) {
    add(l, v);
    if (r < n) add(r + 1, -v);
  }
  inline long long qry(int l, int r) { return sum(r) - sum(l - 1); }
} seg1;
struct SegmentTreeBeats {
  int mx[MAXN << 2], mx2[MAXN << 2], cnt[MAXN << 2], tag[MAXN << 2];
  inline void puttag(int rt, int tg) { mx[rt] = tag[rt] = tg; }
  inline void pushdown(int rt) {
    if (tag[rt]) {
      int tmp = max(mx[(rt << 1)], mx[(rt << 1) | 1]);
      if (mx[(rt << 1)] == tmp) {
        puttag((rt << 1), tag[rt]);
      }
      if (mx[(rt << 1) | 1] == tmp) {
        puttag((rt << 1) | 1, tag[rt]);
      }
      tag[rt] = 0;
    }
  }
  inline void pushup(int rt) {
    if (mx[(rt << 1)] == mx[(rt << 1) | 1]) {
      mx[rt] = mx[(rt << 1)];
      mx2[rt] = max(mx2[(rt << 1)], mx2[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1)] + cnt[(rt << 1) | 1];
    } else if (mx[(rt << 1)] > mx[(rt << 1) | 1]) {
      mx[rt] = mx[(rt << 1)];
      mx2[rt] = max(mx2[(rt << 1)], mx[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1)];
    } else {
      mx[rt] = mx[(rt << 1) | 1];
      mx2[rt] = max(mx[(rt << 1)], mx2[(rt << 1) | 1]);
      cnt[rt] = cnt[(rt << 1) | 1];
    }
  }
  void Build(int rt, int b, int e) {
    if (b == e) {
      mx[rt] = b;
      mx2[rt] = 0;
      cnt[rt] = 1;
      return;
    }
    int mid = (b + e) >> 1;
    Build((rt << 1), b, mid);
    Build((rt << 1) | 1, mid + 1, e);
    pushup(rt);
  }
  void Insert(int rt, int b, int e, int p, int v) {
    if (b == e) {
      seg1.upd(b, mx[rt], -1);
      mx[rt] = v;
      seg1.upd(b, mx[rt], 1);
      return;
    }
    int mid = (b + e) >> 1;
    pushdown(rt);
    if (p <= mid)
      Insert((rt << 1), b, mid, p, v);
    else
      Insert((rt << 1) | 1, mid + 1, e, p, v);
    pushup(rt);
  }
  void UpdateMin(int rt, int b, int e, int l, int r, int v) {
    if (mx[rt] <= v) return;
    if (l <= b && e <= r && v > mx2[rt]) {
      seg1.upd(v + 1, mx[rt], -cnt[rt]);
      puttag(rt, v);
      return;
    }
    int mid = (b + e) >> 1;
    pushdown(rt);
    if (l <= mid) UpdateMin((rt << 1), b, mid, l, r, v);
    if (r > mid) UpdateMin((rt << 1) | 1, mid + 1, e, l, r, v);
    pushup(rt);
  }
} seg2;
void solve() {
  read(n);
  read(q);
  seg1.upd(1, n, 1);
  seg2.Build(1, 1, n);
  int type, l, r;
  while (q--) {
    read(type);
    read(l);
    read(r);
    if (type == 1) {
      seg2.Insert(1, 1, n, l, r);
      if (l > 1) seg2.UpdateMin(1, 1, n, 1, l - 1, l - 1);
    } else {
      printf("%lld\n", seg1.qry(l, r));
    }
  }
}
int main() {
  solve();
  return 0;
}

```