#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
using P = pair<int, int>;

int main() {
  int n, m;
  cin >> n >> m;
  vector<P> ps(m);
  REP(i, m) {
    cin >> ps[i].first >> ps[i].second, ps[i].second--;
  }
  sort(begin(ps), end(ps));
  vector<int> l(n), r(n);
  REP(i, n) l[i] = r[i] = i;
  REP(i, m) {
    int x, y;
    tie(x, y) = ps[i];
    l[y] = min(l[y], l[y + 1]);
    r[y] = max(r[y], r[y + 1]);
    l[y + 1] = min(l[y], l[y + 1]);
    r[y + 1] = max(r[y], r[y + 1]);
  }
  REP(i, n) {
    cout << r[i] - l[i] + 1 << ((i == n - 1) ? '\n' : ' '); 
  }
}



### Prompt

Please create a solution in CPP 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>
#define FOR(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
using P = pair<int, int>;

int main() {
  int n, m;
  cin >> n >> m;
  vector<P> ps(m);
  REP(i, m) {
    cin >> ps[i].first >> ps[i].second, ps[i].second--;
  }
  sort(begin(ps), end(ps));
  vector<int> l(n), r(n);
  REP(i, n) l[i] = r[i] = i;
  REP(i, m) {
    int x, y;
    tie(x, y) = ps[i];
    l[y] = min(l[y], l[y + 1]);
    r[y] = max(r[y], r[y + 1]);
    l[y + 1] = min(l[y], l[y + 1]);
    r[y + 1] = max(r[y], r[y + 1]);
  }
  REP(i, n) {
    cout << r[i] - l[i] + 1 << ((i == n - 1) ? '\n' : ' '); 
  }
}



```