#include<bits/stdc++.h>
#define N 200005
#define M 100005
#define s second
#define f first
using namespace std;
typedef pair<int,int> P;
int n,m;
P p[M],A[N];

void merge(int a,int b){
  A[a]=A[b]=P(min(A[a].f,A[b].f),max(A[a].s,A[b].s));
}

void solve(){
  for(int i=1;i<=n;i++)
    A[i]=P(i,i);
  for(int i=0;i<m;i++)
    merge(p[i].second,p[i].second+1);
  for(int i=1;i<=n;i++){
    if(i!=1)cout<<' ';
    cout<<A[i].second-A[i].first+1;
  }
  cout<<endl;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++)
    cin>>p[i].first>>p[i].second;
  sort(p,p+m);
  solve();
  return 0;
}
### Prompt

Your challenge is to write a cpp solution 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 N 200005
#define M 100005
#define s second
#define f first
using namespace std;
typedef pair<int,int> P;
int n,m;
P p[M],A[N];

void merge(int a,int b){
  A[a]=A[b]=P(min(A[a].f,A[b].f),max(A[a].s,A[b].s));
}

void solve(){
  for(int i=1;i<=n;i++)
    A[i]=P(i,i);
  for(int i=0;i<m;i++)
    merge(p[i].second,p[i].second+1);
  for(int i=1;i<=n;i++){
    if(i!=1)cout<<' ';
    cout<<A[i].second-A[i].first+1;
  }
  cout<<endl;
}

int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++)
    cin>>p[i].first>>p[i].second;
  sort(p,p+m);
  solve();
  return 0;
}
```