#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a[300001],f[300001][2][2],mem[300001][2];
pair<int,int>b[300001];
set<int>s;
int main(){
  r(i,300001)a[i]=1;
  cin>>n>>m;
  r(i,m)cin>>b[i].first>>b[i].second;
  sort(b,b+m);
  r(i,m){
    int x=b[i].second;
    if(!s.count(x)){
      s.insert(x);
      int x1=a[x],x2=a[x-1];
      a[x]+=x2,a[x-1]+=x1;
      if(f[x][0][0]){f[x][1][0]++;}
      else{
        mem[x][0]=a[x];
        f[x][0][0]++;
      }
      if(f[x-1][0][1])f[x-1][1][1]++;
      else{
        mem[x-1][1]=a[x-1];
        f[x-1][0][1]++;
      }
    }
    else{
      if(f[x][1]&&f[x-1][1]){
        int x1=a[x]-mem[x][0],x2=a[x-1]-mem[x-1][1];
        a[x]+=x2,a[x-1]+=x1;
        mem[x][0]=a[x],mem[x-1][1]=a[x-1];
        f[x][1][0]=f[x-1][1][1]=0;
      }
      else if(f[x][1]){
        a[x-1]+=a[x]-a[x-1];
        mem[x-1][1]=a[x-1];
        f[x][1][0]==0;
      }
      else if(f[x-1][1]){
        a[x]+=a[x-1]-a[x];
        mem[x][1]=a[x];
        f[x-1][1][1]=0;
      }
    }
  }
  r(i,n){
    if(i)cout<<' ';
    cout<<a[i];
  }
  cout<<endl;
}
### Prompt

Your task is to create 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 r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a[300001],f[300001][2][2],mem[300001][2];
pair<int,int>b[300001];
set<int>s;
int main(){
  r(i,300001)a[i]=1;
  cin>>n>>m;
  r(i,m)cin>>b[i].first>>b[i].second;
  sort(b,b+m);
  r(i,m){
    int x=b[i].second;
    if(!s.count(x)){
      s.insert(x);
      int x1=a[x],x2=a[x-1];
      a[x]+=x2,a[x-1]+=x1;
      if(f[x][0][0]){f[x][1][0]++;}
      else{
        mem[x][0]=a[x];
        f[x][0][0]++;
      }
      if(f[x-1][0][1])f[x-1][1][1]++;
      else{
        mem[x-1][1]=a[x-1];
        f[x-1][0][1]++;
      }
    }
    else{
      if(f[x][1]&&f[x-1][1]){
        int x1=a[x]-mem[x][0],x2=a[x-1]-mem[x-1][1];
        a[x]+=x2,a[x-1]+=x1;
        mem[x][0]=a[x],mem[x-1][1]=a[x-1];
        f[x][1][0]=f[x-1][1][1]=0;
      }
      else if(f[x][1]){
        a[x-1]+=a[x]-a[x-1];
        mem[x-1][1]=a[x-1];
        f[x][1][0]==0;
      }
      else if(f[x-1][1]){
        a[x]+=a[x-1]-a[x];
        mem[x][1]=a[x];
        f[x-1][1][1]=0;
      }
    }
  }
  r(i,n){
    if(i)cout<<' ';
    cout<<a[i];
  }
  cout<<endl;
}
```