#include <bits/stdc++.h>
using namespace std;
int INF = 1000000;
template <typename T>
struct range_chmin{
  int N;
  vector<T> ST;
  range_chmin(vector<T> A){
    N = 1;
    int n = A.size();
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, INF);
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  T operator [](int k){
    k += N - 1;
    T ans = ST[k];
    while (k > 0){
      k = (k - 1) / 2;
      ans = min(ans, ST[k]);
    }
    return ans;
  }
  void chmin(int L, int R, T x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = min(ST[i], x);
    } else {
      int m = (l + r) / 2;
      chmin(L, R, x, i * 2 + 1, l, m);
      chmin(L, R, x, i * 2 + 2, m, r);
    }
  }
  void chmin(int L, int R, T x){
    chmin(L, R, x, 0, 0, N);
  }
};
template <typename T>
struct range_chmax{
  int N;
  vector<T> ST;
  range_chmax(vector<int> A){
    N = 1;
    int n = A.size();
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, -INF);
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  T operator [](int k){
    k += N - 1;
    T ans = ST[k];
    while (k > 0){
      k = (k - 1) / 2;
      ans = max(ans, ST[k]);
    }
    return ans;
  }
  void chmax(int L, int R, T x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = max(ST[i], x);
    } else {
      int m = (l + r) / 2;
      chmax(L, R, x, i * 2 + 1, l, m);
      chmax(L, R, x, i * 2 + 2, m, r);
    }
  }
  void chmax(int L, int R, T x){
    chmax(L, R, x, 0, 0, N);
  }
};
int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> p(m);
  for (int i = 0; i < m; i++){
    int x, y;
    cin >> x >> y;
    y--;
    p[i] = make_pair(x, y);
  }
  sort(p.begin(), p.end());
  vector<int> pos(n);
  for (int i = 0; i < n; i++){
    pos[i] = i;
  }
  range_chmin<int> L(pos);
  range_chmax<int> R(pos);
  for (int i = 0; i < m; i++){
    int y = p[i].second;
    int tv1 = -1;
    int fv1 = n;
    while (fv1 - tv1 > 1){
      int mid = (tv1 + fv1) / 2;
      if (L[mid] <= y + 1){
        tv1 = mid;
      } else {
        fv1 = mid;
      }
    }
    L.chmin(0, fv1, y);
    int tv2 = n;
    int fv2 = -1;
    while (tv2 - fv2 > 1){
      int mid = (tv2 + fv2) / 2;
      if (R[mid] >= y){
        tv2 = mid;
      } else {
        fv2 = mid;
      }
    }
    R.chmax(tv2, n, y + 1);
  }
  vector<int> d(n + 1, 0);
  for (int i = 0; i < n; i++){
    d[L[i]]++;
    d[R[i] + 1]--;
  }
  for (int i = 0; i < n; i++){
    d[i + 1] += d[i];
  }
  for (int i = 0; i < n; i++){
    cout << d[i];
    if (i < n - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int INF = 1000000;
template <typename T>
struct range_chmin{
  int N;
  vector<T> ST;
  range_chmin(vector<T> A){
    N = 1;
    int n = A.size();
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, INF);
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  T operator [](int k){
    k += N - 1;
    T ans = ST[k];
    while (k > 0){
      k = (k - 1) / 2;
      ans = min(ans, ST[k]);
    }
    return ans;
  }
  void chmin(int L, int R, T x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = min(ST[i], x);
    } else {
      int m = (l + r) / 2;
      chmin(L, R, x, i * 2 + 1, l, m);
      chmin(L, R, x, i * 2 + 2, m, r);
    }
  }
  void chmin(int L, int R, T x){
    chmin(L, R, x, 0, 0, N);
  }
};
template <typename T>
struct range_chmax{
  int N;
  vector<T> ST;
  range_chmax(vector<int> A){
    N = 1;
    int n = A.size();
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, -INF);
    for (int i = 0; i < n; i++){
      ST[N - 1 + i] = A[i];
    }
  }
  T operator [](int k){
    k += N - 1;
    T ans = ST[k];
    while (k > 0){
      k = (k - 1) / 2;
      ans = max(ans, ST[k]);
    }
    return ans;
  }
  void chmax(int L, int R, T x, int i, int l, int r){
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      ST[i] = max(ST[i], x);
    } else {
      int m = (l + r) / 2;
      chmax(L, R, x, i * 2 + 1, l, m);
      chmax(L, R, x, i * 2 + 2, m, r);
    }
  }
  void chmax(int L, int R, T x){
    chmax(L, R, x, 0, 0, N);
  }
};
int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> p(m);
  for (int i = 0; i < m; i++){
    int x, y;
    cin >> x >> y;
    y--;
    p[i] = make_pair(x, y);
  }
  sort(p.begin(), p.end());
  vector<int> pos(n);
  for (int i = 0; i < n; i++){
    pos[i] = i;
  }
  range_chmin<int> L(pos);
  range_chmax<int> R(pos);
  for (int i = 0; i < m; i++){
    int y = p[i].second;
    int tv1 = -1;
    int fv1 = n;
    while (fv1 - tv1 > 1){
      int mid = (tv1 + fv1) / 2;
      if (L[mid] <= y + 1){
        tv1 = mid;
      } else {
        fv1 = mid;
      }
    }
    L.chmin(0, fv1, y);
    int tv2 = n;
    int fv2 = -1;
    while (tv2 - fv2 > 1){
      int mid = (tv2 + fv2) / 2;
      if (R[mid] >= y){
        tv2 = mid;
      } else {
        fv2 = mid;
      }
    }
    R.chmax(tv2, n, y + 1);
  }
  vector<int> d(n + 1, 0);
  for (int i = 0; i < n; i++){
    d[L[i]]++;
    d[R[i] + 1]--;
  }
  for (int i = 0; i < n; i++){
    d[i + 1] += d[i];
  }
  for (int i = 0; i < n; i++){
    cout << d[i];
    if (i < n - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

```