#include <bits/stdc++.h>
using std::max;
using std::min;
const int N = 200005;
int n, q;
int sum[N];
long long sum1[N];
inline void add(int p, int v) {
  while (p <= n) sum[p] += v, p += p & (-p);
}
inline int ask(int p) {
  int ret = 0;
  while (p) ret += sum[p], p -= p & (-p);
  return ret;
}
inline void add1(int p, int v) {
  while (p <= n) sum1[p] += v, p += p & (-p);
}
inline long long ask1(int p) {
  long long ret = 0;
  while (p) ret += sum1[p], p -= p & (-p);
  return ret;
}
inline void radd(int l, int r, int v) {
  add(l, v), add1(l, 1ll * l * v);
  add(r + 1, -v), add1(r + 1, -1ll * (r + 1) * v);
}
inline long long rask(int p) { return 1ll * (p + 1) * ask(p) - ask1(p); }
namespace SGT {
int mx[N << 2], mx1[N << 2], cnt[N << 2], tag[N << 2];
inline void pushdown(int id) {
  mx[(id << 1)] = min(mx[(id << 1)], tag[id]);
  tag[(id << 1)] = min(tag[(id << 1)], tag[id]);
  mx[(id << 1 | 1)] = min(mx[(id << 1 | 1)], tag[id]);
  tag[(id << 1 | 1)] = min(tag[(id << 1 | 1)], tag[id]);
  tag[id] = 0x3f3f3f3f;
}
inline void upt(int id) {
  mx1[id] = 0;
  mx[id] = max(mx[(id << 1)], mx[(id << 1 | 1)]);
  cnt[id] = (mx[(id << 1)] == mx[id] ? cnt[(id << 1)] : 0) +
            (mx[(id << 1 | 1)] == mx[id] ? cnt[(id << 1 | 1)] : 0);
  mx1[id] = max(
      (mx[(id << 1)] == mx[id] ? mx1[(id << 1)] : mx[(id << 1)]),
      (mx[(id << 1 | 1)] == mx[id] ? mx1[(id << 1 | 1)] : mx[(id << 1 | 1)]));
}
void build(int id, int l, int r) {
  tag[id] = 0x3f3f3f3f;
  if (l == r) {
    mx[id] = l;
    cnt[id] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build((id << 1), l, mid), build((id << 1 | 1), mid + 1, r);
  upt(id);
}
void addp(int id, int l, int r, int p, int v) {
  if (l == r) {
    radd(l + 1, mx[id], -1);
    mx[id] = v;
    radd(l + 1, v, 1);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(id);
  if (p <= mid)
    addp((id << 1), l, mid, p, v);
  else
    addp((id << 1 | 1), mid + 1, r, p, v);
  upt(id);
}
void add(int id, int l, int r, int p) {
  if (mx[id] <= p) return;
  if (r <= p) {
    if (mx1[id] < p) {
      radd(p + 1, mx[id], -cnt[id]);
      tag[id] = p;
      mx[id] = p;
      return;
    }
  }
  pushdown(id);
  int mid = (l + r) >> 1;
  add((id << 1), l, mid, p);
  if (p > mid) add((id << 1 | 1), mid + 1, r, p);
  upt(id);
}
}  // namespace SGT
using namespace SGT;
int main() {
  scanf("%d%d", &n, &q);
  build(1, 1, n);
  for (int i = 1, tp, x, y; i <= q; ++i) {
    scanf("%d%d%d", &tp, &x, &y);
    if (tp == 1) {
      if (x - 1) add(1, 1, n, x - 1);
      addp(1, 1, n, x, y);
    } else
      printf("%lld\n", rask(y) - rask(x - 1) + y - x + 1);
  }
  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 std::max;
using std::min;
const int N = 200005;
int n, q;
int sum[N];
long long sum1[N];
inline void add(int p, int v) {
  while (p <= n) sum[p] += v, p += p & (-p);
}
inline int ask(int p) {
  int ret = 0;
  while (p) ret += sum[p], p -= p & (-p);
  return ret;
}
inline void add1(int p, int v) {
  while (p <= n) sum1[p] += v, p += p & (-p);
}
inline long long ask1(int p) {
  long long ret = 0;
  while (p) ret += sum1[p], p -= p & (-p);
  return ret;
}
inline void radd(int l, int r, int v) {
  add(l, v), add1(l, 1ll * l * v);
  add(r + 1, -v), add1(r + 1, -1ll * (r + 1) * v);
}
inline long long rask(int p) { return 1ll * (p + 1) * ask(p) - ask1(p); }
namespace SGT {
int mx[N << 2], mx1[N << 2], cnt[N << 2], tag[N << 2];
inline void pushdown(int id) {
  mx[(id << 1)] = min(mx[(id << 1)], tag[id]);
  tag[(id << 1)] = min(tag[(id << 1)], tag[id]);
  mx[(id << 1 | 1)] = min(mx[(id << 1 | 1)], tag[id]);
  tag[(id << 1 | 1)] = min(tag[(id << 1 | 1)], tag[id]);
  tag[id] = 0x3f3f3f3f;
}
inline void upt(int id) {
  mx1[id] = 0;
  mx[id] = max(mx[(id << 1)], mx[(id << 1 | 1)]);
  cnt[id] = (mx[(id << 1)] == mx[id] ? cnt[(id << 1)] : 0) +
            (mx[(id << 1 | 1)] == mx[id] ? cnt[(id << 1 | 1)] : 0);
  mx1[id] = max(
      (mx[(id << 1)] == mx[id] ? mx1[(id << 1)] : mx[(id << 1)]),
      (mx[(id << 1 | 1)] == mx[id] ? mx1[(id << 1 | 1)] : mx[(id << 1 | 1)]));
}
void build(int id, int l, int r) {
  tag[id] = 0x3f3f3f3f;
  if (l == r) {
    mx[id] = l;
    cnt[id] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build((id << 1), l, mid), build((id << 1 | 1), mid + 1, r);
  upt(id);
}
void addp(int id, int l, int r, int p, int v) {
  if (l == r) {
    radd(l + 1, mx[id], -1);
    mx[id] = v;
    radd(l + 1, v, 1);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(id);
  if (p <= mid)
    addp((id << 1), l, mid, p, v);
  else
    addp((id << 1 | 1), mid + 1, r, p, v);
  upt(id);
}
void add(int id, int l, int r, int p) {
  if (mx[id] <= p) return;
  if (r <= p) {
    if (mx1[id] < p) {
      radd(p + 1, mx[id], -cnt[id]);
      tag[id] = p;
      mx[id] = p;
      return;
    }
  }
  pushdown(id);
  int mid = (l + r) >> 1;
  add((id << 1), l, mid, p);
  if (p > mid) add((id << 1 | 1), mid + 1, r, p);
  upt(id);
}
}  // namespace SGT
using namespace SGT;
int main() {
  scanf("%d%d", &n, &q);
  build(1, 1, n);
  for (int i = 1, tp, x, y; i <= q; ++i) {
    scanf("%d%d%d", &tp, &x, &y);
    if (tp == 1) {
      if (x - 1) add(1, 1, n, x - 1);
      addp(1, 1, n, x, y);
    } else
      printf("%lld\n", rask(y) - rask(x - 1) + y - x + 1);
  }
  return 0;
}

```