#include <bits/stdc++.h>
using namespace std;

#define REP(i, s, e) for(int i = (int)(s); i < (int)(e); ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

int main() {
  int n, m;
  cin >> n >> m;
  using P = pair<int, int>;
  vector<P> v(m);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --y;
    v[i] = {x, y};
  }
  sort(v.begin(), v.end());

  vector<P> ans(n);
  rep(i, n) ans[i] = {i, i+1};
  rep(i, m) {
    int x = v[i].second;
    int y = x + 1;
    ans[x].first = min(ans[x].first, ans[y].first);
    ans[x].second = max(ans[x].second, ans[y].second);
    ans[y].first = min(ans[x].first, ans[y].first);
    ans[y].second = max(ans[x].second, ans[y].second);
  }
  rep(i, n) {
    cout << ans[i].second-ans[i].first << (i+1 == n ? '\n' : ' ');
  }
  return 0;
}


### Prompt

Construct a Cpp code solution to the problem outlined:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define REP(i, s, e) for(int i = (int)(s); i < (int)(e); ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

int main() {
  int n, m;
  cin >> n >> m;
  using P = pair<int, int>;
  vector<P> v(m);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    --y;
    v[i] = {x, y};
  }
  sort(v.begin(), v.end());

  vector<P> ans(n);
  rep(i, n) ans[i] = {i, i+1};
  rep(i, m) {
    int x = v[i].second;
    int y = x + 1;
    ans[x].first = min(ans[x].first, ans[y].first);
    ans[x].second = max(ans[x].second, ans[y].second);
    ans[y].first = min(ans[x].first, ans[y].first);
    ans[y].second = max(ans[x].second, ans[y].second);
  }
  rep(i, n) {
    cout << ans[i].second-ans[i].first << (i+1 == n ? '\n' : ' ');
  }
  return 0;
}


```