#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

//#define DEBUG

struct point {
  int main;
  int sub;
  point() = default;
  point(int m, int s): main(m), sub(s) {}
};

struct arm {
  int x, y;
  arm() = default;
  bool operator<(const arm& lhs) const {
    return this->x < lhs.x;
  }
};

#ifdef DEBUG
#define dump(i) cout << "[*] " #i ": " << i << endl;
template <class T>
void print(const vector<T>& vec) {
  for (const T& v : vec) {
    dump(v);
  }
}
template <>
void print(const vector<arm>& arms) {
  for (const arm& a : arms) {
    dump(a.x);
    dump(a.y);
  }
}
template <>
void print(const vector<point>& points) {
  for (const point& p : points) {
    dump(p.main);
    dump(p.sub);
  }
}
template <>
void print(const vector<set<int>>& sets) {
  for (const set<int>& se: sets) {
    cout << "[*] { ";
    for (const int& s : se) {
      cout << s << " ";
    }
    cout << "}" << endl;
  }
}
#define line() cout << " ---- " << endl;
#else
#define dump(i)
#define print(i)
#define line()
#endif

int main() {
  int n, m;
  cin >> n >> m;
  vector<arm> arms(m);
  for (int i = 0; i < m; ++i) {
    cin >> arms[i].x >> arms[i].y;
  }
  vector<pair<int, int>> r(n+1);
  for (int i = 0; i < n+1; ++i) {
    r[i].first = r[i].second = i;
  }

  sort(arms.begin(), arms.end());

  for (const arm& a : arms) {
    r[a.y].second = max(r[a.y].second, r[a.y+1].second);
    r[a.y+1].first = min(r[a.y+1].first, r[a.y].first);
  }

  for (int i = 1; i <= n; ++i) {
    cout << r[i].second -  r[i].first + 1;
    if (i != n) {
      cout << " ";
    }
  }
  cout << endl;
  return 0;
}


### 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 <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

//#define DEBUG

struct point {
  int main;
  int sub;
  point() = default;
  point(int m, int s): main(m), sub(s) {}
};

struct arm {
  int x, y;
  arm() = default;
  bool operator<(const arm& lhs) const {
    return this->x < lhs.x;
  }
};

#ifdef DEBUG
#define dump(i) cout << "[*] " #i ": " << i << endl;
template <class T>
void print(const vector<T>& vec) {
  for (const T& v : vec) {
    dump(v);
  }
}
template <>
void print(const vector<arm>& arms) {
  for (const arm& a : arms) {
    dump(a.x);
    dump(a.y);
  }
}
template <>
void print(const vector<point>& points) {
  for (const point& p : points) {
    dump(p.main);
    dump(p.sub);
  }
}
template <>
void print(const vector<set<int>>& sets) {
  for (const set<int>& se: sets) {
    cout << "[*] { ";
    for (const int& s : se) {
      cout << s << " ";
    }
    cout << "}" << endl;
  }
}
#define line() cout << " ---- " << endl;
#else
#define dump(i)
#define print(i)
#define line()
#endif

int main() {
  int n, m;
  cin >> n >> m;
  vector<arm> arms(m);
  for (int i = 0; i < m; ++i) {
    cin >> arms[i].x >> arms[i].y;
  }
  vector<pair<int, int>> r(n+1);
  for (int i = 0; i < n+1; ++i) {
    r[i].first = r[i].second = i;
  }

  sort(arms.begin(), arms.end());

  for (const arm& a : arms) {
    r[a.y].second = max(r[a.y].second, r[a.y+1].second);
    r[a.y+1].first = min(r[a.y+1].first, r[a.y].first);
  }

  for (int i = 1; i <= n; ++i) {
    cout << r[i].second -  r[i].first + 1;
    if (i != n) {
      cout << " ";
    }
  }
  cout << endl;
  return 0;
}


```