#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
void ckmn(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void ckmx(T& a, T b) {
  a = max(a, b);
}
void rd(int& x) { scanf("%i", &x); }
void rd(long long& x) { scanf("%lld", &x); }
void rd(char* x) { scanf("%s", x); }
void rd(double& x) { scanf("%lf", &x); }
void rd(string& x) { scanf("%s", &x); }
template <typename T1, typename T2>
void rd(pair<T1, T2>& x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(vector<T>& x) {
  for (T& i : x) rd(i);
}
template <typename T, typename... A>
void rd(T& x, A&... args) {
  rd(x);
  rd(args...);
}
template <typename T>
void rd() {
  T x;
  rd(x);
  return x;
}
int ri() {
  int x;
  rd(x);
  return x;
}
template <typename T>
vector<T> rv(int n) {
  vector<T> x(n);
  rd(x);
  return x;
}
template <typename T>
void ra(T a[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]);
}
template <typename T1, typename T2>
void ra(T1 a[], T2 b[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]);
}
template <typename T1, typename T2, typename T3>
void ra(T1 a[], T2 b[], T3 c[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]), rd(c[st + i]);
}
void re(vector<int> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    rd(u, v);
    E[u].push_back(v);
    if (!dir) E[v].push_back(u);
  }
}
template <typename T>
void re(vector<pair<int, T>> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    T w;
    rd(u, v, w);
    E[u].push_back({v, w});
    if (!dir) E[v].push_back({u, w});
  }
}
const int N = 200050;
const int M = 2 * N;
namespace SegLazy {
int ls[M], rs[M], tsz, root;
long long sum[M], lzy[M];
void Build(int& c, int ss, int se) {
  c = ++tsz;
  sum[c] = se - ss + 1;
  lzy[c] = 0;
  if (ss == se) return;
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
}
void upd(int c, int ss, int se, long long x) {
  sum[c] += x * (se - ss + 1);
  lzy[c] += x;
}
void push(int c, int ss, int se) {
  if (!lzy[c]) return;
  int mid = ss + se >> 1;
  upd(ls[c], ss, mid, lzy[c]);
  upd(rs[c], mid + 1, se, lzy[c]);
  lzy[c] = 0;
}
void Add(int c, int ss, int se, int qs, int qe, long long x) {
  if (qs > qe || qs > se || ss > qe) return;
  if (qs <= ss && qe >= se) {
    upd(c, ss, se, x);
    return;
  }
  int mid = ss + se >> 1;
  push(c, ss, se);
  Add(ls[c], ss, mid, qs, qe, x);
  Add(rs[c], mid + 1, se, qs, qe, x);
  sum[c] = sum[ls[c]] + sum[rs[c]];
}
long long Get(int c, int ss, int se, int qs, int qe) {
  if (qs > qe || qs > se || ss > qe) return 0;
  if (qs <= ss && qe >= se) return sum[c];
  int mid = ss + se >> 1;
  push(c, ss, se);
  return Get(ls[c], ss, mid, qs, qe) + Get(rs[c], mid + 1, se, qs, qe);
}
}  // namespace SegLazy
int n, q;
int ls[M], rs[M], tsz, root, mx[M], smx[M], cnt[M], lzy[M];
void Build(int& c, int ss, int se) {
  c = ++tsz;
  mx[c] = se;
  smx[c] = se - 1;
  cnt[c] = 1;
  lzy[c] = n + 1;
  if (ss == se) {
    smx[c] = 0;
    return;
  }
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
}
void upd(int c, int x) {
  if (mx[c] > x) {
    mx[c] = x;
    lzy[c] = x;
  }
}
void push(int c) {
  if (lzy[c] != n + 1) {
    upd(ls[c], lzy[c]);
    upd(rs[c], lzy[c]);
    lzy[c] = n + 1;
  }
}
void pull(int c) {
  if (mx[ls[c]] > mx[rs[c]]) {
    mx[c] = mx[ls[c]];
    smx[c] = max(smx[ls[c]], mx[rs[c]]);
    cnt[c] = cnt[ls[c]];
  } else if (mx[rs[c]] > mx[ls[c]]) {
    mx[c] = mx[rs[c]];
    smx[c] = max(mx[ls[c]], smx[rs[c]]);
    cnt[c] = cnt[rs[c]];
  } else {
    mx[c] = mx[ls[c]];
    smx[c] = max(smx[ls[c]], smx[rs[c]]);
    cnt[c] = cnt[ls[c]] + cnt[rs[c]];
  }
}
void Set(int c, int ss, int se, int qi, int x) {
  if (ss == se) {
    SegLazy::Add(SegLazy::root, 1, n, qi, mx[c], -1);
    SegLazy::Add(SegLazy::root, 1, n, qi, x, 1);
    mx[c] = x;
    smx[c] = 0;
    cnt[c] = 1;
    return;
  }
  int mid = ss + se >> 1;
  push(c);
  if (qi <= mid)
    Set(ls[c], ss, mid, qi, x);
  else
    Set(rs[c], mid + 1, se, qi, x);
  pull(c);
}
void Min(int c, int ss, int se, int qs, int qe, int x) {
  if (qs > qe || qs > se || ss > qe || mx[c] <= x) return;
  if (qs <= ss & qe >= se && smx[c] < x) {
    SegLazy::Add(SegLazy::root, 1, n, x + 1, mx[c], -cnt[c]);
    upd(c, x);
    return;
  }
  int mid = ss + se >> 1;
  push(c);
  Min(ls[c], ss, mid, qs, qe, x);
  Min(rs[c], mid + 1, se, qs, qe, x);
  pull(c);
}
int main() {
  scanf("%i %i", &n, &q);
  SegLazy::Build(SegLazy::root, 1, n);
  Build(root, 1, n);
  while (q--) {
    int t, a, b;
    scanf("%i %i %i", &t, &a, &b);
    if (t == 1) {
      Set(root, 1, n, a, b);
      Min(root, 1, n, 1, a - 1, a - 1);
    } else {
      printf("%lld\n", SegLazy::Get(SegLazy::root, 1, n, a, b));
    }
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T>
void ckmn(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void ckmx(T& a, T b) {
  a = max(a, b);
}
void rd(int& x) { scanf("%i", &x); }
void rd(long long& x) { scanf("%lld", &x); }
void rd(char* x) { scanf("%s", x); }
void rd(double& x) { scanf("%lf", &x); }
void rd(string& x) { scanf("%s", &x); }
template <typename T1, typename T2>
void rd(pair<T1, T2>& x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(vector<T>& x) {
  for (T& i : x) rd(i);
}
template <typename T, typename... A>
void rd(T& x, A&... args) {
  rd(x);
  rd(args...);
}
template <typename T>
void rd() {
  T x;
  rd(x);
  return x;
}
int ri() {
  int x;
  rd(x);
  return x;
}
template <typename T>
vector<T> rv(int n) {
  vector<T> x(n);
  rd(x);
  return x;
}
template <typename T>
void ra(T a[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]);
}
template <typename T1, typename T2>
void ra(T1 a[], T2 b[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]);
}
template <typename T1, typename T2, typename T3>
void ra(T1 a[], T2 b[], T3 c[], int n, int st = 1) {
  for (int i = 0; i < n; ++i) rd(a[st + i]), rd(b[st + i]), rd(c[st + i]);
}
void re(vector<int> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    rd(u, v);
    E[u].push_back(v);
    if (!dir) E[v].push_back(u);
  }
}
template <typename T>
void re(vector<pair<int, T>> E[], int m, bool dir = 0) {
  for (int i = 0, u, v; i < m; ++i) {
    T w;
    rd(u, v, w);
    E[u].push_back({v, w});
    if (!dir) E[v].push_back({u, w});
  }
}
const int N = 200050;
const int M = 2 * N;
namespace SegLazy {
int ls[M], rs[M], tsz, root;
long long sum[M], lzy[M];
void Build(int& c, int ss, int se) {
  c = ++tsz;
  sum[c] = se - ss + 1;
  lzy[c] = 0;
  if (ss == se) return;
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
}
void upd(int c, int ss, int se, long long x) {
  sum[c] += x * (se - ss + 1);
  lzy[c] += x;
}
void push(int c, int ss, int se) {
  if (!lzy[c]) return;
  int mid = ss + se >> 1;
  upd(ls[c], ss, mid, lzy[c]);
  upd(rs[c], mid + 1, se, lzy[c]);
  lzy[c] = 0;
}
void Add(int c, int ss, int se, int qs, int qe, long long x) {
  if (qs > qe || qs > se || ss > qe) return;
  if (qs <= ss && qe >= se) {
    upd(c, ss, se, x);
    return;
  }
  int mid = ss + se >> 1;
  push(c, ss, se);
  Add(ls[c], ss, mid, qs, qe, x);
  Add(rs[c], mid + 1, se, qs, qe, x);
  sum[c] = sum[ls[c]] + sum[rs[c]];
}
long long Get(int c, int ss, int se, int qs, int qe) {
  if (qs > qe || qs > se || ss > qe) return 0;
  if (qs <= ss && qe >= se) return sum[c];
  int mid = ss + se >> 1;
  push(c, ss, se);
  return Get(ls[c], ss, mid, qs, qe) + Get(rs[c], mid + 1, se, qs, qe);
}
}  // namespace SegLazy
int n, q;
int ls[M], rs[M], tsz, root, mx[M], smx[M], cnt[M], lzy[M];
void Build(int& c, int ss, int se) {
  c = ++tsz;
  mx[c] = se;
  smx[c] = se - 1;
  cnt[c] = 1;
  lzy[c] = n + 1;
  if (ss == se) {
    smx[c] = 0;
    return;
  }
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
}
void upd(int c, int x) {
  if (mx[c] > x) {
    mx[c] = x;
    lzy[c] = x;
  }
}
void push(int c) {
  if (lzy[c] != n + 1) {
    upd(ls[c], lzy[c]);
    upd(rs[c], lzy[c]);
    lzy[c] = n + 1;
  }
}
void pull(int c) {
  if (mx[ls[c]] > mx[rs[c]]) {
    mx[c] = mx[ls[c]];
    smx[c] = max(smx[ls[c]], mx[rs[c]]);
    cnt[c] = cnt[ls[c]];
  } else if (mx[rs[c]] > mx[ls[c]]) {
    mx[c] = mx[rs[c]];
    smx[c] = max(mx[ls[c]], smx[rs[c]]);
    cnt[c] = cnt[rs[c]];
  } else {
    mx[c] = mx[ls[c]];
    smx[c] = max(smx[ls[c]], smx[rs[c]]);
    cnt[c] = cnt[ls[c]] + cnt[rs[c]];
  }
}
void Set(int c, int ss, int se, int qi, int x) {
  if (ss == se) {
    SegLazy::Add(SegLazy::root, 1, n, qi, mx[c], -1);
    SegLazy::Add(SegLazy::root, 1, n, qi, x, 1);
    mx[c] = x;
    smx[c] = 0;
    cnt[c] = 1;
    return;
  }
  int mid = ss + se >> 1;
  push(c);
  if (qi <= mid)
    Set(ls[c], ss, mid, qi, x);
  else
    Set(rs[c], mid + 1, se, qi, x);
  pull(c);
}
void Min(int c, int ss, int se, int qs, int qe, int x) {
  if (qs > qe || qs > se || ss > qe || mx[c] <= x) return;
  if (qs <= ss & qe >= se && smx[c] < x) {
    SegLazy::Add(SegLazy::root, 1, n, x + 1, mx[c], -cnt[c]);
    upd(c, x);
    return;
  }
  int mid = ss + se >> 1;
  push(c);
  Min(ls[c], ss, mid, qs, qe, x);
  Min(rs[c], mid + 1, se, qs, qe, x);
  pull(c);
}
int main() {
  scanf("%i %i", &n, &q);
  SegLazy::Build(SegLazy::root, 1, n);
  Build(root, 1, n);
  while (q--) {
    int t, a, b;
    scanf("%i %i %i", &t, &a, &b);
    if (t == 1) {
      Set(root, 1, n, a, b);
      Min(root, 1, n, 1, a - 1, a - 1);
    } else {
      printf("%lld\n", SegLazy::Get(SegLazy::root, 1, n, a, b));
    }
  }
  return 0;
}

```