#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
signed main() {
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<int> lower(N), upper(N);
  REP(i,N) {
    upper[i] = lower[i] = i;
  }
  vector<pair<int, int>> B;
  REP(i,M) {
    int a, b; cin >> a >> b;
    b--;
    B.emplace_back(a, b);
  }
  sort(B.begin(), B.end());
  for(const auto &item : B) {
    int k = item.second;
    upper[k] = upper[k + 1] = max(upper[k], upper[k + 1]);
    lower[k] = lower[k + 1] = min(lower[k], lower[k + 1]);
  }
  REP(i,N) {
    if(i > 0) cout << ' ';
    cout << upper[i] - lower[i] + 1;
  }
  cout << endl;
}
### Prompt

Create a solution in cpp for 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;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
signed main() {
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<int> lower(N), upper(N);
  REP(i,N) {
    upper[i] = lower[i] = i;
  }
  vector<pair<int, int>> B;
  REP(i,M) {
    int a, b; cin >> a >> b;
    b--;
    B.emplace_back(a, b);
  }
  sort(B.begin(), B.end());
  for(const auto &item : B) {
    int k = item.second;
    upper[k] = upper[k + 1] = max(upper[k], upper[k + 1]);
    lower[k] = lower[k + 1] = min(lower[k], lower[k + 1]);
  }
  REP(i,N) {
    if(i > 0) cout << ' ';
    cout << upper[i] - lower[i] + 1;
  }
  cout << endl;
}
```