#include <bits/stdc++.h>
using namespace std;
int n, Q;
class ZYK {
  class BIT {
    long long b[200020];
    inline int lowbit(int x) { return x & (-x); }

   public:
    inline void Add(int x, long long d) {
      while (x <= n) b[x] += d, x += lowbit(x);
    }
    inline long long Ask(int x) {
      long long ans = 0;
      while (x) ans += b[x], x -= lowbit(x);
      return ans;
    }
  } B1, B2;

 public:
  void Change(int l, int r, int d) {
    B1.Add(l, d), B1.Add(r + 1, -d);
    B2.Add(l, 1LL * l * d), B2.Add(r + 1, -1LL * (r + 1) * d);
  }
  long long Query(int l, int r) {
    return (1LL * (r + 1) * B1.Ask(r) - B2.Ask(r)) -
           (1LL * l * B1.Ask(l - 1) - B2.Ask(l - 1));
  }
} B;
class Seg {
  struct node {
    int mx, se, add, cnt;
    inline void Add(int d) { add += d, mx += d; }
    friend node operator+(const node &a, const node &b) {
      node c;
      c.mx = max(a.mx, b.mx);
      c.cnt = 0;
      if (c.mx == a.mx) c.cnt += a.cnt;
      if (c.mx == b.mx) c.cnt += b.cnt;
      c.se = max(c.mx == a.mx ? a.se : a.mx, c.mx == b.mx ? b.se : b.mx);
      return c;
    }
  } t[200020 << 2];
  inline void pushdown(int u) {
    if (t[u].add) {
      if (t[u << 1].mx + t[u].add == t[u].mx) t[u << 1].Add(t[u].add);
      if (t[u << 1 | 1].mx + t[u].add == t[u].mx) t[u << 1 | 1].Add(t[u].add);
      t[u].add = 0;
    }
  }

 public:
  void build(int u, int L, int R) {
    if (L == R) {
      t[u].mx = L;
      t[u].se = 0;
      B.Change(L, L, 1);
      t[u].cnt = 1;
      return;
    }
    int mid = (L + R) >> 1;
    build(u << 1, L, mid), build(u << 1 | 1, mid + 1, R);
  }
  void Min(int u, int L, int R, int l, int r, int d) {
    if (d >= t[u].mx) return;
    if (L >= l && R <= r && d > t[u].se) {
      B.Change(d + 1, t[u].mx, -t[u].cnt);
      t[u].Add(d - t[u].mx);
      return;
    }
    pushdown(u);
    int mid = (L + R) >> 1;
    if (l <= mid) Min(u << 1, L, mid, l, r, d);
    if (r > mid) Min(u << 1 | 1, mid + 1, R, l, r, d);
    t[u] = t[u << 1] + t[u << 1 | 1];
  }
  int Find(int u, int L, int R, int p) {
    if (L == R) return t[u].mx;
    pushdown(u);
    int mid = (L + R) >> 1;
    return p <= mid ? Find(u << 1, L, mid, p) : Find(u << 1 | 1, mid + 1, R, p);
  }
  void Change(int u, int L, int R, int p, int d) {
    if (L == R) {
      t[u].mx = d;
      return;
    }
    int mid = (L + R) >> 1;
    pushdown(u);
    p <= mid ? Change(u << 1, L, mid, p, d)
             : Change(u << 1 | 1, mid + 1, R, p, d);
    t[u] = t[u << 1] + t[u << 1 | 1];
  }
} T;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> Q;
  T.build(1, 1, n);
  while (Q--) {
    int opt, x, y;
    cin >> opt >> x >> y;
    if (opt == 1) {
      if (x > 1) T.Min(1, 1, n, 1, x - 1, x - 1);
      int z = T.Find(1, 1, n, x);
      B.Change(x, z, -1);
      T.Change(1, 1, n, x, y);
      B.Change(x, y, 1);
    } else {
      cout << B.Query(x, y) << '\n';
    }
  }
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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;
int n, Q;
class ZYK {
  class BIT {
    long long b[200020];
    inline int lowbit(int x) { return x & (-x); }

   public:
    inline void Add(int x, long long d) {
      while (x <= n) b[x] += d, x += lowbit(x);
    }
    inline long long Ask(int x) {
      long long ans = 0;
      while (x) ans += b[x], x -= lowbit(x);
      return ans;
    }
  } B1, B2;

 public:
  void Change(int l, int r, int d) {
    B1.Add(l, d), B1.Add(r + 1, -d);
    B2.Add(l, 1LL * l * d), B2.Add(r + 1, -1LL * (r + 1) * d);
  }
  long long Query(int l, int r) {
    return (1LL * (r + 1) * B1.Ask(r) - B2.Ask(r)) -
           (1LL * l * B1.Ask(l - 1) - B2.Ask(l - 1));
  }
} B;
class Seg {
  struct node {
    int mx, se, add, cnt;
    inline void Add(int d) { add += d, mx += d; }
    friend node operator+(const node &a, const node &b) {
      node c;
      c.mx = max(a.mx, b.mx);
      c.cnt = 0;
      if (c.mx == a.mx) c.cnt += a.cnt;
      if (c.mx == b.mx) c.cnt += b.cnt;
      c.se = max(c.mx == a.mx ? a.se : a.mx, c.mx == b.mx ? b.se : b.mx);
      return c;
    }
  } t[200020 << 2];
  inline void pushdown(int u) {
    if (t[u].add) {
      if (t[u << 1].mx + t[u].add == t[u].mx) t[u << 1].Add(t[u].add);
      if (t[u << 1 | 1].mx + t[u].add == t[u].mx) t[u << 1 | 1].Add(t[u].add);
      t[u].add = 0;
    }
  }

 public:
  void build(int u, int L, int R) {
    if (L == R) {
      t[u].mx = L;
      t[u].se = 0;
      B.Change(L, L, 1);
      t[u].cnt = 1;
      return;
    }
    int mid = (L + R) >> 1;
    build(u << 1, L, mid), build(u << 1 | 1, mid + 1, R);
  }
  void Min(int u, int L, int R, int l, int r, int d) {
    if (d >= t[u].mx) return;
    if (L >= l && R <= r && d > t[u].se) {
      B.Change(d + 1, t[u].mx, -t[u].cnt);
      t[u].Add(d - t[u].mx);
      return;
    }
    pushdown(u);
    int mid = (L + R) >> 1;
    if (l <= mid) Min(u << 1, L, mid, l, r, d);
    if (r > mid) Min(u << 1 | 1, mid + 1, R, l, r, d);
    t[u] = t[u << 1] + t[u << 1 | 1];
  }
  int Find(int u, int L, int R, int p) {
    if (L == R) return t[u].mx;
    pushdown(u);
    int mid = (L + R) >> 1;
    return p <= mid ? Find(u << 1, L, mid, p) : Find(u << 1 | 1, mid + 1, R, p);
  }
  void Change(int u, int L, int R, int p, int d) {
    if (L == R) {
      t[u].mx = d;
      return;
    }
    int mid = (L + R) >> 1;
    pushdown(u);
    p <= mid ? Change(u << 1, L, mid, p, d)
             : Change(u << 1 | 1, mid + 1, R, p, d);
    t[u] = t[u << 1] + t[u << 1 | 1];
  }
} T;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> Q;
  T.build(1, 1, n);
  while (Q--) {
    int opt, x, y;
    cin >> opt >> x >> y;
    if (opt == 1) {
      if (x > 1) T.Min(1, 1, n, 1, x - 1, x - 1);
      int z = T.Find(1, 1, n, x);
      B.Change(x, z, -1);
      T.Change(1, 1, n, x, y);
      B.Change(x, y, 1);
    } else {
      cout << B.Query(x, y) << '\n';
    }
  }
  return 0;
}

```