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

typedef pair<int,int> P;

P merge(P a,P b){
  int l=min(a.first,b.first);
  int r=max(a.second,b.second);
  return P(l,r);
}

int n,m;
vector< int > G[100001];
P t[200000];

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    t[i]=P(i,i);
  }
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    G[x].push_back(y);
  }
  for(int i=0;i<100001;i++){
    for(int j=0;j<(int)G[i].size();j++){
      int y=G[i][j];
      t[y-1]=t[y]=merge(t[y-1],t[y]);
    }
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<t[i].second-t[i].first+1;
  }
  cout<<endl;
  return 0;
}
### Prompt

In CPP, your task is to solve 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;

typedef pair<int,int> P;

P merge(P a,P b){
  int l=min(a.first,b.first);
  int r=max(a.second,b.second);
  return P(l,r);
}

int n,m;
vector< int > G[100001];
P t[200000];

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    t[i]=P(i,i);
  }
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    G[x].push_back(y);
  }
  for(int i=0;i<100001;i++){
    for(int j=0;j<(int)G[i].size();j++){
      int y=G[i][j];
      t[y-1]=t[y]=merge(t[y-1],t[y]);
    }
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<t[i].second-t[i].first+1;
  }
  cout<<endl;
  return 0;
}
```