#include <bits/stdc++.h>
using namespace std;
int n, m;
struct BIT {
  long long t1[200005], t2[200005];
  void mdf(int p, int v) {
    for (long long x = 1ll * p * v; p <= n; p += (p & -p))
      t1[p] += v, t2[p] += x;
  }
  void mdf(int l, int r, int v) { mdf(l, v), mdf(r + 1, -v); }
  long long _q(int x, long long r1 = 0, long long r2 = 0) {
    for (int p = x; p; p -= (p & -p)) r1 += t1[p], r2 += t2[p];
    return r1 * (x + 1) - r2;
  }
  long long qry(int l, int r) { return _q(r) - _q(l - 1); }
} B;
int mx[200005 << 2], sc[200005 << 2], cnt[200005 << 2], tg[200005 << 2];
void cov(int k, int v) {
  if (v > mx[k]) return;
  mx[k] = tg[k] = v;
}
void pud(int k) {
  if (~tg[k]) cov(k << 1, tg[k]), cov(k << 1 | 1, tg[k]), tg[k] = -1;
}
void upd(int k) {
  int ls = k << 1, rs = k << 1 | 1;
  mx[k] = max(mx[ls], mx[rs]);
  cnt[k] = 0;
  sc[k] = -1;
  if (mx[k] == mx[ls])
    cnt[k] += cnt[ls], sc[k] = max(sc[k], sc[ls]);
  else
    sc[k] = max(sc[k], mx[ls]);
  if (mx[k] == mx[rs])
    cnt[k] += cnt[rs], sc[k] = max(sc[k], sc[rs]);
  else
    sc[k] = max(sc[k], mx[rs]);
}
void build(int k, int l, int r) {
  tg[k] = -1;
  if (l == r) {
    mx[k] = l, sc[k] = -1, cnt[k] = 1, B.mdf(l, l, 1);
    return;
  }
  int mid = l + r >> 1;
  build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
  upd(k);
}
void Min(int k, int l, int r, int x, int y, int v) {
  if (v >= mx[k]) return;
  if (x <= l && r <= y && v > sc[k])
    return B.mdf(v + 1, mx[k], -cnt[k]), cov(k, v);
  pud(k);
  int mid = l + r >> 1;
  if (x <= mid) Min(k << 1, l, mid, x, y, v);
  if (y > mid) Min(k << 1 | 1, mid + 1, r, x, y, v);
  upd(k);
}
void mdf(int k, int l, int r, int x, int v) {
  if (l == r) {
    B.mdf(l, mx[k], -1), mx[k] = v, tg[k] = -1, B.mdf(l, v, 1);
    return;
  }
  pud(k);
  int mid = l + r >> 1;
  (x <= mid) ? mdf(k << 1, l, mid, x, v) : mdf(k << 1 | 1, mid + 1, r, x, v);
  upd(k);
}
int main() {
  scanf("%d%d", &n, &m);
  build(1, 1, n);
  for (int opt, x, y; m--;) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      if (x > 1) Min(1, 1, n, 1, x - 1, x - 1);
      mdf(1, 1, n, x, y);
    } else
      printf("%lld\n", B.qry(x, y));
  }
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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, m;
struct BIT {
  long long t1[200005], t2[200005];
  void mdf(int p, int v) {
    for (long long x = 1ll * p * v; p <= n; p += (p & -p))
      t1[p] += v, t2[p] += x;
  }
  void mdf(int l, int r, int v) { mdf(l, v), mdf(r + 1, -v); }
  long long _q(int x, long long r1 = 0, long long r2 = 0) {
    for (int p = x; p; p -= (p & -p)) r1 += t1[p], r2 += t2[p];
    return r1 * (x + 1) - r2;
  }
  long long qry(int l, int r) { return _q(r) - _q(l - 1); }
} B;
int mx[200005 << 2], sc[200005 << 2], cnt[200005 << 2], tg[200005 << 2];
void cov(int k, int v) {
  if (v > mx[k]) return;
  mx[k] = tg[k] = v;
}
void pud(int k) {
  if (~tg[k]) cov(k << 1, tg[k]), cov(k << 1 | 1, tg[k]), tg[k] = -1;
}
void upd(int k) {
  int ls = k << 1, rs = k << 1 | 1;
  mx[k] = max(mx[ls], mx[rs]);
  cnt[k] = 0;
  sc[k] = -1;
  if (mx[k] == mx[ls])
    cnt[k] += cnt[ls], sc[k] = max(sc[k], sc[ls]);
  else
    sc[k] = max(sc[k], mx[ls]);
  if (mx[k] == mx[rs])
    cnt[k] += cnt[rs], sc[k] = max(sc[k], sc[rs]);
  else
    sc[k] = max(sc[k], mx[rs]);
}
void build(int k, int l, int r) {
  tg[k] = -1;
  if (l == r) {
    mx[k] = l, sc[k] = -1, cnt[k] = 1, B.mdf(l, l, 1);
    return;
  }
  int mid = l + r >> 1;
  build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
  upd(k);
}
void Min(int k, int l, int r, int x, int y, int v) {
  if (v >= mx[k]) return;
  if (x <= l && r <= y && v > sc[k])
    return B.mdf(v + 1, mx[k], -cnt[k]), cov(k, v);
  pud(k);
  int mid = l + r >> 1;
  if (x <= mid) Min(k << 1, l, mid, x, y, v);
  if (y > mid) Min(k << 1 | 1, mid + 1, r, x, y, v);
  upd(k);
}
void mdf(int k, int l, int r, int x, int v) {
  if (l == r) {
    B.mdf(l, mx[k], -1), mx[k] = v, tg[k] = -1, B.mdf(l, v, 1);
    return;
  }
  pud(k);
  int mid = l + r >> 1;
  (x <= mid) ? mdf(k << 1, l, mid, x, v) : mdf(k << 1 | 1, mid + 1, r, x, v);
  upd(k);
}
int main() {
  scanf("%d%d", &n, &m);
  build(1, 1, n);
  for (int opt, x, y; m--;) {
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 1) {
      if (x > 1) Min(1, 1, n, 1, x - 1, x - 1);
      mdf(1, 1, n, x, y);
    } else
      printf("%lld\n", B.qry(x, y));
  }
}

```