#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
  int N, M; cin >> N >> M;
  vector< pair<int, int> > lr(N);
  for(int i=0; i<N; i++) lr[i] = make_pair(i, i);

  vector< pair<int, int> > info(M);
  for(int i=0; i<M; i++) {
    cin >> info[i].first >> info[i].second;
  }
  sort(info.begin(), info.end());

  for(int i=0; i<M; i++) {
    int y = info[i].second;
    auto &A = lr[y-1], &B = lr[y];

    int mi = min(A.first, B.first);
    int ma = max(A.second, B.second);

    pair<int, int> newElem(mi, ma);
    A = B = newElem;
  }

  for(int i=0; i<N; i++) {
    cout << lr[i].second - lr[i].first + 1 << " \n"[i+1==N];
  }
  return 0;
}


### 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 <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
  int N, M; cin >> N >> M;
  vector< pair<int, int> > lr(N);
  for(int i=0; i<N; i++) lr[i] = make_pair(i, i);

  vector< pair<int, int> > info(M);
  for(int i=0; i<M; i++) {
    cin >> info[i].first >> info[i].second;
  }
  sort(info.begin(), info.end());

  for(int i=0; i<M; i++) {
    int y = info[i].second;
    auto &A = lr[y-1], &B = lr[y];

    int mi = min(A.first, B.first);
    int ma = max(A.second, B.second);

    pair<int, int> newElem(mi, ma);
    A = B = newElem;
  }

  for(int i=0; i<N; i++) {
    cout << lr[i].second - lr[i].first + 1 << " \n"[i+1==N];
  }
  return 0;
}


```