#include <bits/stdc++.h>
using namespace std;
inline long long readint() {
  long long x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f ? -x : x;
}
int n, q;
struct node1 {
  int l, r;
  node1* ch[2];
  long long sum, add = 0;
  void pushup() { sum = ch[0]->sum + ch[1]->sum; }
  node1(int l, int r) : l(l), r(r), sum(r - l + 1) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    ch[0] = new node1(l, mid);
    ch[1] = new node1(mid + 1, r);
  }
  void pushtag(long long k) {
    sum += k * (r - l + 1);
    add += k;
  }
  void pushdown() {
    ch[0]->pushtag(add);
    ch[1]->pushtag(add);
    add = 0;
  }
  void modify(int ql, int qr, long long k) {
    if (ql <= l && qr >= r) {
      pushtag(k);
      return;
    }
    pushdown();
    if (ql <= ch[0]->r) ch[0]->modify(ql, qr, k);
    if (qr >= ch[1]->l) ch[1]->modify(ql, qr, k);
    pushup();
  }
  long long query(int ql, int qr) {
    if (ql <= l && qr >= r) return sum;
    pushdown();
    long long ans = 0;
    if (ql <= ch[0]->r) ans += ch[0]->query(ql, qr);
    if (qr >= ch[1]->l) ans += ch[1]->query(ql, qr);
    return ans;
  }
} * rt1;
struct node2 {
  int l, r;
  node2* ch[2];
  int mx, mx2, cnt = 1, add = 0;
  void pushup() {
    if (ch[0]->mx > ch[1]->mx) {
      mx = ch[0]->mx;
      mx2 = max(ch[0]->mx2, ch[1]->mx);
      cnt = ch[0]->cnt;
    } else if (ch[0]->mx < ch[1]->mx) {
      mx = ch[1]->mx;
      mx2 = max(ch[1]->mx2, ch[0]->mx);
      cnt = ch[1]->cnt;
    } else {
      mx = ch[0]->mx;
      mx2 = max(ch[0]->mx2, ch[1]->mx2);
      cnt = ch[0]->cnt + ch[1]->cnt;
    }
  }
  node2(int l, int r) : l(l), r(r), mx(r), mx2(l == r ? 0 : r - 1) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    ch[0] = new node2(l, mid);
    ch[1] = new node2(mid + 1, r);
  }
  void pushtag(int k) {
    mx += k;
    add += k;
  }
  void pushdown() {
    if (ch[0]->mx > ch[1]->mx)
      ch[0]->pushtag(add);
    else if (ch[0]->mx < ch[1]->mx)
      ch[1]->pushtag(add);
    else {
      ch[0]->pushtag(add);
      ch[1]->pushtag(add);
    }
    add = 0;
  }
  void modify1(int x, int k) {
    if (l == r) {
      rt1->modify(x, mx, -1);
      rt1->modify(x, mx = k, 1);
      return;
    }
    pushdown();
    if (x <= ch[0]->r)
      ch[0]->modify1(x, k);
    else
      ch[1]->modify1(x, k);
    pushup();
  }
  void modify2(int ql, int qr, int k) {
    if (k >= mx) return;
    if (ql <= l && qr >= r && k >= mx2) {
      rt1->modify(k + 1, mx, -cnt);
      pushtag(k - mx);
      return;
    }
    pushdown();
    if (ql <= ch[0]->r) ch[0]->modify2(ql, qr, k);
    if (qr >= ch[1]->l) ch[1]->modify2(ql, qr, k);
    pushup();
  }
} * rt2;
int main() {
  n = readint();
  q = readint();
  rt1 = new node1(1, n);
  rt2 = new node2(1, n);
  while (q--) {
    int p = readint();
    if (p == 1) {
      int c, g;
      c = readint();
      g = readint();
      rt2->modify1(c, g);
      if (c > 1) rt2->modify2(1, c - 1, c - 1);
    } else {
      int l, r;
      l = readint();
      r = readint();
      printf("%lld\n", rt1->query(l, r));
    }
  }
  return 0;
}

### Prompt

Develop a solution in CPP 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;
inline long long readint() {
  long long x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return f ? -x : x;
}
int n, q;
struct node1 {
  int l, r;
  node1* ch[2];
  long long sum, add = 0;
  void pushup() { sum = ch[0]->sum + ch[1]->sum; }
  node1(int l, int r) : l(l), r(r), sum(r - l + 1) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    ch[0] = new node1(l, mid);
    ch[1] = new node1(mid + 1, r);
  }
  void pushtag(long long k) {
    sum += k * (r - l + 1);
    add += k;
  }
  void pushdown() {
    ch[0]->pushtag(add);
    ch[1]->pushtag(add);
    add = 0;
  }
  void modify(int ql, int qr, long long k) {
    if (ql <= l && qr >= r) {
      pushtag(k);
      return;
    }
    pushdown();
    if (ql <= ch[0]->r) ch[0]->modify(ql, qr, k);
    if (qr >= ch[1]->l) ch[1]->modify(ql, qr, k);
    pushup();
  }
  long long query(int ql, int qr) {
    if (ql <= l && qr >= r) return sum;
    pushdown();
    long long ans = 0;
    if (ql <= ch[0]->r) ans += ch[0]->query(ql, qr);
    if (qr >= ch[1]->l) ans += ch[1]->query(ql, qr);
    return ans;
  }
} * rt1;
struct node2 {
  int l, r;
  node2* ch[2];
  int mx, mx2, cnt = 1, add = 0;
  void pushup() {
    if (ch[0]->mx > ch[1]->mx) {
      mx = ch[0]->mx;
      mx2 = max(ch[0]->mx2, ch[1]->mx);
      cnt = ch[0]->cnt;
    } else if (ch[0]->mx < ch[1]->mx) {
      mx = ch[1]->mx;
      mx2 = max(ch[1]->mx2, ch[0]->mx);
      cnt = ch[1]->cnt;
    } else {
      mx = ch[0]->mx;
      mx2 = max(ch[0]->mx2, ch[1]->mx2);
      cnt = ch[0]->cnt + ch[1]->cnt;
    }
  }
  node2(int l, int r) : l(l), r(r), mx(r), mx2(l == r ? 0 : r - 1) {
    if (l == r) return;
    int mid = l + (r - l) / 2;
    ch[0] = new node2(l, mid);
    ch[1] = new node2(mid + 1, r);
  }
  void pushtag(int k) {
    mx += k;
    add += k;
  }
  void pushdown() {
    if (ch[0]->mx > ch[1]->mx)
      ch[0]->pushtag(add);
    else if (ch[0]->mx < ch[1]->mx)
      ch[1]->pushtag(add);
    else {
      ch[0]->pushtag(add);
      ch[1]->pushtag(add);
    }
    add = 0;
  }
  void modify1(int x, int k) {
    if (l == r) {
      rt1->modify(x, mx, -1);
      rt1->modify(x, mx = k, 1);
      return;
    }
    pushdown();
    if (x <= ch[0]->r)
      ch[0]->modify1(x, k);
    else
      ch[1]->modify1(x, k);
    pushup();
  }
  void modify2(int ql, int qr, int k) {
    if (k >= mx) return;
    if (ql <= l && qr >= r && k >= mx2) {
      rt1->modify(k + 1, mx, -cnt);
      pushtag(k - mx);
      return;
    }
    pushdown();
    if (ql <= ch[0]->r) ch[0]->modify2(ql, qr, k);
    if (qr >= ch[1]->l) ch[1]->modify2(ql, qr, k);
    pushup();
  }
} * rt2;
int main() {
  n = readint();
  q = readint();
  rt1 = new node1(1, n);
  rt2 = new node2(1, n);
  while (q--) {
    int p = readint();
    if (p == 1) {
      int c, g;
      c = readint();
      g = readint();
      rt2->modify1(c, g);
      if (c > 1) rt2->modify2(1, c - 1, c - 1);
    } else {
      int l, r;
      l = readint();
      r = readint();
      printf("%lld\n", rt1->query(l, r));
    }
  }
  return 0;
}

```