#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 14;
int n, q;
struct SegmentLazy {
  int lazy[MAX_N << 2];
  long long s[MAX_N << 2];
  void build(int id = 1, int l = 0, int r = n) {
    if (r - l < 2) {
      s[id] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
    s[id] = s[id << 1] + s[id << 1 | 1];
  }
  void up(int id, int l, int r, int x) {
    lazy[id] += x;
    s[id] += long long(r - l) * x;
  }
  void shift(int id, int l, int r) {
    int mid = (l + r) >> 1;
    up(id << 1, l, mid, lazy[id]);
    up(id << 1 | 1, mid, r, lazy[id]);
    lazy[id] = 0;
  }
  void add(int st, int en, int v, int id = 1, int l = 0, int r = n) {
    if (en <= l || r <= st) return;
    if (st <= l && r <= en) {
      up(id, l, r, v);
      return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    add(st, en, v, id << 1, l, mid);
    add(st, en, v, id << 1 | 1, mid, r);
    s[id] = s[id << 1] + s[id << 1 | 1];
  }
  long long sum(int st, int en, int id = 1, int l = 0, int r = n) {
    if (en <= l || r <= st) return 0;
    if (st <= l && r <= en) return s[id];
    shift(id, l, r);
    int mid = (l + r) >> 1;
    return sum(st, en, id << 1, l, mid) + sum(st, en, id << 1 | 1, mid, r);
  }
} segment_lazy;
struct SegmentBeats {
  struct Node {
    int m, c, s;
    Node operator+(const Node &o) const {
      if (m > o.m) return {m, c, max(s, o.m)};
      if (m < o.m) return {o.m, o.c, max(o.s, m)};
      return {m, c + o.c, max(s, o.s)};
    }
  } seg[MAX_N * 4];
  int lazy[MAX_N * 4];
  SegmentBeats() { memset(lazy, -1, sizeof lazy); }
  void build(int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) {
      seg[id] = {r, 1, -1};
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
  void up(int id, int x) {
    if (seg[id].m <= x) return;
    lazy[id] = seg[id].m = x;
  }
  void shift(int id) {
    if (lazy[id] == -1) return;
    up(id * 2, lazy[id]);
    up(id * 2 + 1, lazy[id]);
    lazy[id] = -1;
  }
  int get(int p, int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) return seg[id].m;
    shift(id);
    int mid = (l + r) / 2;
    return (p < mid ? get(p, l, mid, id * 2) : get(p, mid, r, id * 2 + 1));
  }
  void modify(int p, int x, int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) {
      seg[id].m = x;
      return;
    }
    shift(id);
    int mid = (l + r) / 2;
    if (p < mid)
      modify(p, x, l, mid, id * 2);
    else
      modify(p, x, mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
  void upd(int s, int e, int x, int l = 0, int r = n, int id = 1) {
    if (e <= l || r <= s || seg[id].m <= x) return;
    if (s <= l && r <= e && seg[id].s < x) {
      segment_lazy.add(x, seg[id].m, -seg[id].c);
      up(id, x);
      return;
    }
    shift(id);
    int mid = (l + r) / 2;
    upd(s, e, x, l, mid, id * 2);
    upd(s, e, x, mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
} segment_beats;
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  segment_lazy.build();
  segment_beats.build();
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int c, g;
      cin >> c >> g;
      --c;
      int pw = segment_beats.get(c);
      segment_lazy.add(c, pw, -1);
      segment_lazy.add(c, g, +1);
      segment_beats.upd(0, c, c);
      segment_beats.modify(c, g);
    } else {
      int l, r;
      cin >> l >> r;
      cout << segment_lazy.sum(--l, r) << '\n';
    }
  }
}

### Prompt

Create a solution in Cpp for 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;
const int MAX_N = 2e5 + 14;
int n, q;
struct SegmentLazy {
  int lazy[MAX_N << 2];
  long long s[MAX_N << 2];
  void build(int id = 1, int l = 0, int r = n) {
    if (r - l < 2) {
      s[id] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
    s[id] = s[id << 1] + s[id << 1 | 1];
  }
  void up(int id, int l, int r, int x) {
    lazy[id] += x;
    s[id] += long long(r - l) * x;
  }
  void shift(int id, int l, int r) {
    int mid = (l + r) >> 1;
    up(id << 1, l, mid, lazy[id]);
    up(id << 1 | 1, mid, r, lazy[id]);
    lazy[id] = 0;
  }
  void add(int st, int en, int v, int id = 1, int l = 0, int r = n) {
    if (en <= l || r <= st) return;
    if (st <= l && r <= en) {
      up(id, l, r, v);
      return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    add(st, en, v, id << 1, l, mid);
    add(st, en, v, id << 1 | 1, mid, r);
    s[id] = s[id << 1] + s[id << 1 | 1];
  }
  long long sum(int st, int en, int id = 1, int l = 0, int r = n) {
    if (en <= l || r <= st) return 0;
    if (st <= l && r <= en) return s[id];
    shift(id, l, r);
    int mid = (l + r) >> 1;
    return sum(st, en, id << 1, l, mid) + sum(st, en, id << 1 | 1, mid, r);
  }
} segment_lazy;
struct SegmentBeats {
  struct Node {
    int m, c, s;
    Node operator+(const Node &o) const {
      if (m > o.m) return {m, c, max(s, o.m)};
      if (m < o.m) return {o.m, o.c, max(o.s, m)};
      return {m, c + o.c, max(s, o.s)};
    }
  } seg[MAX_N * 4];
  int lazy[MAX_N * 4];
  SegmentBeats() { memset(lazy, -1, sizeof lazy); }
  void build(int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) {
      seg[id] = {r, 1, -1};
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
  void up(int id, int x) {
    if (seg[id].m <= x) return;
    lazy[id] = seg[id].m = x;
  }
  void shift(int id) {
    if (lazy[id] == -1) return;
    up(id * 2, lazy[id]);
    up(id * 2 + 1, lazy[id]);
    lazy[id] = -1;
  }
  int get(int p, int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) return seg[id].m;
    shift(id);
    int mid = (l + r) / 2;
    return (p < mid ? get(p, l, mid, id * 2) : get(p, mid, r, id * 2 + 1));
  }
  void modify(int p, int x, int l = 0, int r = n, int id = 1) {
    if (l + 1 == r) {
      seg[id].m = x;
      return;
    }
    shift(id);
    int mid = (l + r) / 2;
    if (p < mid)
      modify(p, x, l, mid, id * 2);
    else
      modify(p, x, mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
  void upd(int s, int e, int x, int l = 0, int r = n, int id = 1) {
    if (e <= l || r <= s || seg[id].m <= x) return;
    if (s <= l && r <= e && seg[id].s < x) {
      segment_lazy.add(x, seg[id].m, -seg[id].c);
      up(id, x);
      return;
    }
    shift(id);
    int mid = (l + r) / 2;
    upd(s, e, x, l, mid, id * 2);
    upd(s, e, x, mid, r, id * 2 + 1);
    seg[id] = seg[id * 2] + seg[id * 2 + 1];
  }
} segment_beats;
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  segment_lazy.build();
  segment_beats.build();
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int c, g;
      cin >> c >> g;
      --c;
      int pw = segment_beats.get(c);
      segment_lazy.add(c, pw, -1);
      segment_lazy.add(c, g, +1);
      segment_beats.upd(0, c, c);
      segment_beats.modify(c, g);
    } else {
      int l, r;
      cin >> l >> r;
      cout << segment_lazy.sum(--l, r) << '\n';
    }
  }
}

```