#include <bits/stdc++.h>
using namespace std;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
const int N = 200005, INF = 0X3F3F3F3F;
int n, Q;
struct seg2 {
  long long t[N * 4], tg[N * 4];
  int length[N * 4];
  void pst(int k1, long long k2) {
    tg[k1] += k2;
    t[k1] += k2 * length[k1];
  }
  void psd(int k1) {
    if (tg[k1]) {
      pst(k1 * 2, tg[k1]);
      pst(k1 * 2 + 1, tg[k1]);
      tg[k1] = 0;
    }
  }
  void upd(int k1) { t[k1] = t[k1 * 2] + t[k1 * 2 + 1]; }
  void bud(int k1, int k2, int k3) {
    length[k1] = k3 - k2 + 1;
    if (k2 == k3) {
      t[k1] = 1;
      return;
    }
    int mid = (k2 + k3) >> 1;
    bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
    upd(k1);
  }
  void add(int k1, int k2, int k3, int k4, int k5, int k6) {
    if (k2 > k5 || k3 < k4) return;
    if (k4 <= k2 && k3 <= k5) {
      pst(k1, k6);
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    add(k1 * 2, k2, mid, k4, k5, k6), add(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
    upd(k1);
  }
  long long res;
  void ask(int k1, int k2, int k3, int k4, int k5) {
    if (k2 > k5 || k3 < k4) return;
    if (k4 <= k2 && k3 <= k5) {
      res += t[k1];
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    ask(k1 * 2, k2, mid, k4, k5), ask(k1 * 2 + 1, mid + 1, k3, k4, k5);
  }
  long long ask(int l, int r) {
    res = 0;
    ask(1, 1, n, l, r);
    return res;
  }
  void out(int k1, int k2, int k3) {
    if (k2 == k3) {
      ((void)0);
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
  }
  void out() {
    ((void)0);
    out(1, 1, n), ((void)0);
  }
} T;
int mx[N * 4], cnt[N * 4], mx_[N * 4];
void upd(int k1) {
  if (mx[k1 * 2] == mx[k1 * 2 + 1]) {
    mx[k1] = mx[k1 * 2];
    cnt[k1] = cnt[k1 * 2] + cnt[k1 * 2 + 1];
    mx_[k1] = max(mx_[k1 * 2], mx_[k1 * 2 + 1]);
  } else if (mx[k1 * 2] > mx[k1 * 2 + 1]) {
    mx[k1] = mx[k1 * 2];
    cnt[k1] = cnt[k1 * 2];
    mx_[k1] = max(mx_[k1 * 2], mx[k1 * 2 + 1]);
  } else {
    mx[k1] = mx[k1 * 2 + 1];
    cnt[k1] = cnt[k1 * 2 + 1];
    mx_[k1] = max(mx_[k1 * 2 + 1], mx[k1 * 2]);
  }
}
void bud(int k1, int k2, int k3) {
  if (k2 == k3) {
    mx[k1] = k2, mx_[k1] = ~INF;
    cnt[k1] = 1;
    return;
  }
  int mid = (k2 + k3) >> 1;
  bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
  upd(k1);
}
void mdf(int k1, int k2, int k3, int k4, int k5, int k6) {
  if (k2 > k5 || k3 < k4 || mx[k1] <= k6) return;
  if (k4 <= k2 && k3 <= k5) {
    if (mx_[k1] < k6) {
      T.add(1, 1, n, k6 + 1, mx[k1], -cnt[k1]);
      mx[k1] = k6;
      return;
    }
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  mdf(k1 * 2, k2, mid, k4, k5, k6), mdf(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
  upd(k1);
}
void chg(int k1, int k2, int k3, int k4, int k5) {
  if (k2 == k3) {
    if (k2 < mx[k1]) {
      T.add(1, 1, n, k2 + 1, mx[k1], -1);
    }
    mx[k1] = k5;
    if (k2 < mx[k1]) {
      T.add(1, 1, n, k2 + 1, mx[k1], 1);
    }
    return;
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  if (k4 <= mid)
    chg(k1 * 2, k2, mid, k4, k5);
  else
    chg(k1 * 2 + 1, mid + 1, k3, k4, k5);
  upd(k1);
}
void out(int k1, int k2, int k3) {
  if (k2 == k3) {
    ((void)0);
    return;
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
  upd(k1);
}
int main() {
  rd(n), rd(Q);
  T.bud(1, 1, n);
  bud(1, 1, n);
  for (int i = (1); i <= (Q); ++i) {
    int tp;
    rd(tp);
    if (tp == 1) {
      int c, g;
      rd(c), rd(g);
      if (1 <= c - 1) mdf(1, 1, n, 1, c - 1, c - 1);
      chg(1, 1, n, c, g);
    } else {
      int l, r;
      rd(l), rd(r);
      printf("%lld\n", T.ask(l, r));
    }
  }
  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;
template <typename T>
void rd(T& x) {
  int f = 0, c;
  while (!isdigit(c = getchar())) f ^= !(c ^ 45);
  x = (c & 15);
  while (isdigit(c = getchar())) x = x * 10 + (c & 15);
  if (f) x = -x;
}
template <typename T>
void pt(T x, int c = -1) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 + 48);
  if (c != -1) putchar(c);
}
const int N = 200005, INF = 0X3F3F3F3F;
int n, Q;
struct seg2 {
  long long t[N * 4], tg[N * 4];
  int length[N * 4];
  void pst(int k1, long long k2) {
    tg[k1] += k2;
    t[k1] += k2 * length[k1];
  }
  void psd(int k1) {
    if (tg[k1]) {
      pst(k1 * 2, tg[k1]);
      pst(k1 * 2 + 1, tg[k1]);
      tg[k1] = 0;
    }
  }
  void upd(int k1) { t[k1] = t[k1 * 2] + t[k1 * 2 + 1]; }
  void bud(int k1, int k2, int k3) {
    length[k1] = k3 - k2 + 1;
    if (k2 == k3) {
      t[k1] = 1;
      return;
    }
    int mid = (k2 + k3) >> 1;
    bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
    upd(k1);
  }
  void add(int k1, int k2, int k3, int k4, int k5, int k6) {
    if (k2 > k5 || k3 < k4) return;
    if (k4 <= k2 && k3 <= k5) {
      pst(k1, k6);
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    add(k1 * 2, k2, mid, k4, k5, k6), add(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
    upd(k1);
  }
  long long res;
  void ask(int k1, int k2, int k3, int k4, int k5) {
    if (k2 > k5 || k3 < k4) return;
    if (k4 <= k2 && k3 <= k5) {
      res += t[k1];
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    ask(k1 * 2, k2, mid, k4, k5), ask(k1 * 2 + 1, mid + 1, k3, k4, k5);
  }
  long long ask(int l, int r) {
    res = 0;
    ask(1, 1, n, l, r);
    return res;
  }
  void out(int k1, int k2, int k3) {
    if (k2 == k3) {
      ((void)0);
      return;
    }
    psd(k1);
    int mid = (k2 + k3) >> 1;
    out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
  }
  void out() {
    ((void)0);
    out(1, 1, n), ((void)0);
  }
} T;
int mx[N * 4], cnt[N * 4], mx_[N * 4];
void upd(int k1) {
  if (mx[k1 * 2] == mx[k1 * 2 + 1]) {
    mx[k1] = mx[k1 * 2];
    cnt[k1] = cnt[k1 * 2] + cnt[k1 * 2 + 1];
    mx_[k1] = max(mx_[k1 * 2], mx_[k1 * 2 + 1]);
  } else if (mx[k1 * 2] > mx[k1 * 2 + 1]) {
    mx[k1] = mx[k1 * 2];
    cnt[k1] = cnt[k1 * 2];
    mx_[k1] = max(mx_[k1 * 2], mx[k1 * 2 + 1]);
  } else {
    mx[k1] = mx[k1 * 2 + 1];
    cnt[k1] = cnt[k1 * 2 + 1];
    mx_[k1] = max(mx_[k1 * 2 + 1], mx[k1 * 2]);
  }
}
void bud(int k1, int k2, int k3) {
  if (k2 == k3) {
    mx[k1] = k2, mx_[k1] = ~INF;
    cnt[k1] = 1;
    return;
  }
  int mid = (k2 + k3) >> 1;
  bud(k1 * 2, k2, mid), bud(k1 * 2 + 1, mid + 1, k3);
  upd(k1);
}
void mdf(int k1, int k2, int k3, int k4, int k5, int k6) {
  if (k2 > k5 || k3 < k4 || mx[k1] <= k6) return;
  if (k4 <= k2 && k3 <= k5) {
    if (mx_[k1] < k6) {
      T.add(1, 1, n, k6 + 1, mx[k1], -cnt[k1]);
      mx[k1] = k6;
      return;
    }
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  mdf(k1 * 2, k2, mid, k4, k5, k6), mdf(k1 * 2 + 1, mid + 1, k3, k4, k5, k6);
  upd(k1);
}
void chg(int k1, int k2, int k3, int k4, int k5) {
  if (k2 == k3) {
    if (k2 < mx[k1]) {
      T.add(1, 1, n, k2 + 1, mx[k1], -1);
    }
    mx[k1] = k5;
    if (k2 < mx[k1]) {
      T.add(1, 1, n, k2 + 1, mx[k1], 1);
    }
    return;
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  if (k4 <= mid)
    chg(k1 * 2, k2, mid, k4, k5);
  else
    chg(k1 * 2 + 1, mid + 1, k3, k4, k5);
  upd(k1);
}
void out(int k1, int k2, int k3) {
  if (k2 == k3) {
    ((void)0);
    return;
  }
  mx[k1 * 2] = min(mx[k1 * 2], mx[k1]);
  mx[k1 * 2 + 1] = min(mx[k1 * 2 + 1], mx[k1]);
  int mid = (k2 + k3) >> 1;
  out(k1 * 2, k2, mid), out(k1 * 2 + 1, mid + 1, k3);
  upd(k1);
}
int main() {
  rd(n), rd(Q);
  T.bud(1, 1, n);
  bud(1, 1, n);
  for (int i = (1); i <= (Q); ++i) {
    int tp;
    rd(tp);
    if (tp == 1) {
      int c, g;
      rd(c), rd(g);
      if (1 <= c - 1) mdf(1, 1, n, 1, c - 1, c - 1);
      chg(1, 1, n, c, g);
    } else {
      int l, r;
      rd(l), rd(r);
      printf("%lld\n", T.ask(l, r));
    }
  }
  return 0;
}

```