#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 200200;
struct seg_tree {
  ll sum[maxn * 4], lazy[maxn * 4];
  void build(int l, int r, int rt) {
    sum[rt] = r - l + 1;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
  }
  void push_down(int l, int r, int rt) {
    if (lazy[rt]) {
      int mid = (l + r) / 2;
      sum[rt << 1] += (mid - l + 1) * lazy[rt];
      sum[rt << 1 | 1] += (r - mid) * lazy[rt];
      lazy[rt << 1] += lazy[rt];
      lazy[rt << 1 | 1] += lazy[rt];
      lazy[rt] = 0;
    }
  }
  void add(int L, int R, int v, int l, int r, int rt) {
    if (L <= l && r <= R) {
      sum[rt] += v * (ll)(r - l + 1);
      lazy[rt] += v;
      return;
    }
    push_down(l, r, rt);
    int mid = (l + r) / 2;
    if (L <= mid) add(L, R, v, l, mid, rt << 1);
    if (mid < R) add(L, R, v, mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  }
  ll ask(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[rt];
    push_down(l, r, rt);
    int mid = (l + r) / 2;
    ll ans = 0;
    if (L <= mid) ans += ask(L, R, l, mid, rt << 1);
    if (mid < R) ans += ask(L, R, mid + 1, r, rt << 1 | 1);
    return ans;
  }
} S;
struct seg_tree2 {
  int n;
  struct node {
    int mx, mx2, num_mx, tag;
  } tr[maxn * 4];
  void build(int l, int r, int rt) {
    if (l == r) {
      tr[rt].mx = l;
      tr[rt].mx2 = 0;
      tr[rt].num_mx = 1;
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    tr[rt].mx = r;
    tr[rt].mx2 = r - 1;
    tr[rt].num_mx = 1;
  }
  void push_up(int rt) {
    if (tr[rt << 1].mx > tr[rt << 1 | 1].mx) {
      tr[rt].mx = tr[rt << 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx);
      tr[rt].num_mx = tr[rt << 1].num_mx;
    } else if (tr[rt << 1].mx < tr[rt << 1 | 1].mx) {
      tr[rt].mx = tr[rt << 1 | 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx, tr[rt << 1 | 1].mx2);
      tr[rt].num_mx = tr[rt << 1 | 1].num_mx;
    } else {
      tr[rt].mx = tr[rt << 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx2);
      tr[rt].num_mx = tr[rt << 1].num_mx + tr[rt << 1 | 1].num_mx;
    }
  }
  void push_down(int rt) {
    if (tr[rt].tag) {
      if (tr[rt << 1].mx > tr[rt].tag) {
        tr[rt << 1].mx = tr[rt].tag;
        tr[rt << 1].tag = tr[rt].tag;
      }
      if (tr[rt << 1 | 1].mx > tr[rt].tag) {
        tr[rt << 1 | 1].mx = tr[rt].tag;
        tr[rt << 1 | 1].tag = tr[rt].tag;
      }
      tr[rt].tag = 0;
    }
  }
  void upd_min(int L, int R, int v, int l, int r, int rt) {
    if (l > R || r < L || tr[rt].mx <= v) return;
    if (L <= l && r <= R && tr[rt].mx2 < v) {
      S.add(v + 1, tr[rt].mx, -tr[rt].num_mx, 1, n, 1);
      tr[rt].mx = v;
      tr[rt].tag = v;
      return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    upd_min(L, R, v, l, mid, rt << 1);
    upd_min(L, R, v, mid + 1, r, rt << 1 | 1);
    push_up(rt);
  }
  void upd(int p, int v, int l, int r, int rt) {
    if (l == r) {
      if (tr[rt].mx > v) {
        S.add(v + 1, tr[rt].mx, -1, 1, n, 1);
      } else if (tr[rt].mx < v) {
        S.add(tr[rt].mx + 1, v, 1, 1, n, 1);
      }
      tr[rt].mx = v;
      return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (p <= mid)
      upd(p, v, l, mid, rt << 1);
    else
      upd(p, v, mid + 1, r, rt << 1 | 1);
    push_up(rt);
  }
} T;
int main(void) {
  int n, q;
  scanf("%d%d", &n, &q);
  S.build(1, n, 1);
  T.n = n;
  T.build(1, n, 1);
  for (int i = 0; i < q; i++) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      T.upd(x, y, 1, n, 1);
      if (x > 1) T.upd_min(1, x - 1, x - 1, 1, n, 1);
    } else {
      ll ans = S.ask(x, y, 1, n, 1);
      printf("%lld\n", ans);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
using ll = long long;
const int maxn = 200200;
struct seg_tree {
  ll sum[maxn * 4], lazy[maxn * 4];
  void build(int l, int r, int rt) {
    sum[rt] = r - l + 1;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
  }
  void push_down(int l, int r, int rt) {
    if (lazy[rt]) {
      int mid = (l + r) / 2;
      sum[rt << 1] += (mid - l + 1) * lazy[rt];
      sum[rt << 1 | 1] += (r - mid) * lazy[rt];
      lazy[rt << 1] += lazy[rt];
      lazy[rt << 1 | 1] += lazy[rt];
      lazy[rt] = 0;
    }
  }
  void add(int L, int R, int v, int l, int r, int rt) {
    if (L <= l && r <= R) {
      sum[rt] += v * (ll)(r - l + 1);
      lazy[rt] += v;
      return;
    }
    push_down(l, r, rt);
    int mid = (l + r) / 2;
    if (L <= mid) add(L, R, v, l, mid, rt << 1);
    if (mid < R) add(L, R, v, mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  }
  ll ask(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[rt];
    push_down(l, r, rt);
    int mid = (l + r) / 2;
    ll ans = 0;
    if (L <= mid) ans += ask(L, R, l, mid, rt << 1);
    if (mid < R) ans += ask(L, R, mid + 1, r, rt << 1 | 1);
    return ans;
  }
} S;
struct seg_tree2 {
  int n;
  struct node {
    int mx, mx2, num_mx, tag;
  } tr[maxn * 4];
  void build(int l, int r, int rt) {
    if (l == r) {
      tr[rt].mx = l;
      tr[rt].mx2 = 0;
      tr[rt].num_mx = 1;
      return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    tr[rt].mx = r;
    tr[rt].mx2 = r - 1;
    tr[rt].num_mx = 1;
  }
  void push_up(int rt) {
    if (tr[rt << 1].mx > tr[rt << 1 | 1].mx) {
      tr[rt].mx = tr[rt << 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx);
      tr[rt].num_mx = tr[rt << 1].num_mx;
    } else if (tr[rt << 1].mx < tr[rt << 1 | 1].mx) {
      tr[rt].mx = tr[rt << 1 | 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx, tr[rt << 1 | 1].mx2);
      tr[rt].num_mx = tr[rt << 1 | 1].num_mx;
    } else {
      tr[rt].mx = tr[rt << 1].mx;
      tr[rt].mx2 = max(tr[rt << 1].mx2, tr[rt << 1 | 1].mx2);
      tr[rt].num_mx = tr[rt << 1].num_mx + tr[rt << 1 | 1].num_mx;
    }
  }
  void push_down(int rt) {
    if (tr[rt].tag) {
      if (tr[rt << 1].mx > tr[rt].tag) {
        tr[rt << 1].mx = tr[rt].tag;
        tr[rt << 1].tag = tr[rt].tag;
      }
      if (tr[rt << 1 | 1].mx > tr[rt].tag) {
        tr[rt << 1 | 1].mx = tr[rt].tag;
        tr[rt << 1 | 1].tag = tr[rt].tag;
      }
      tr[rt].tag = 0;
    }
  }
  void upd_min(int L, int R, int v, int l, int r, int rt) {
    if (l > R || r < L || tr[rt].mx <= v) return;
    if (L <= l && r <= R && tr[rt].mx2 < v) {
      S.add(v + 1, tr[rt].mx, -tr[rt].num_mx, 1, n, 1);
      tr[rt].mx = v;
      tr[rt].tag = v;
      return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    upd_min(L, R, v, l, mid, rt << 1);
    upd_min(L, R, v, mid + 1, r, rt << 1 | 1);
    push_up(rt);
  }
  void upd(int p, int v, int l, int r, int rt) {
    if (l == r) {
      if (tr[rt].mx > v) {
        S.add(v + 1, tr[rt].mx, -1, 1, n, 1);
      } else if (tr[rt].mx < v) {
        S.add(tr[rt].mx + 1, v, 1, 1, n, 1);
      }
      tr[rt].mx = v;
      return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (p <= mid)
      upd(p, v, l, mid, rt << 1);
    else
      upd(p, v, mid + 1, r, rt << 1 | 1);
    push_up(rt);
  }
} T;
int main(void) {
  int n, q;
  scanf("%d%d", &n, &q);
  S.build(1, n, 1);
  T.n = n;
  T.build(1, n, 1);
  for (int i = 0; i < q; i++) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1) {
      T.upd(x, y, 1, n, 1);
      if (x > 1) T.upd_min(1, x - 1, x - 1, 1, n, 1);
    } else {
      ll ans = S.ask(x, y, 1, n, 1);
      printf("%lld\n", ans);
    }
  }
  return 0;
}

```