#include<bits/stdc++.h>
#define N 200010
#define f first
#define s second
using namespace std;
typedef pair<int,int> P;  

int main(){
  int n,m;
  cin>>n>>m;
  P A[N];
  for(int i=0,x,y;i<m;i++)cin>>x>>y,A[i]=P(x,y-1);
  sort(A,A+m);

  int u[N],d[N];
  for(int i=0;i<n;i++) u[i]=d[i]=i;

  for(int i=0;i<m;i++){
    int y=A[i].s;
    u[y]=max(u[y],u[y+1]);
    d[y+1]=min(d[y+1],d[y]);
  }

  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<(u[i]-i)+(i-d[i])+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>
#define N 200010
#define f first
#define s second
using namespace std;
typedef pair<int,int> P;  

int main(){
  int n,m;
  cin>>n>>m;
  P A[N];
  for(int i=0,x,y;i<m;i++)cin>>x>>y,A[i]=P(x,y-1);
  sort(A,A+m);

  int u[N],d[N];
  for(int i=0;i<n;i++) u[i]=d[i]=i;

  for(int i=0;i<m;i++){
    int y=A[i].s;
    u[y]=max(u[y],u[y+1]);
    d[y+1]=min(d[y+1],d[y]);
  }

  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<(u[i]-i)+(i-d[i])+1;
  }
  cout<<endl;
  return 0;
}
```