#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<pair<int,int> >v;
int ans[N],a[N];
int main()
{
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)ans[i]=1;
    for(i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end());
    memset(a,0,sizeof a);
    for(auto x:v)
    {
        int y=x.second;
        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];
        a[y]=ans[y];
    }
    cout<<ans[1];
    for(i=2;i<=n;i++)printf(" %d",ans[i]);
    cout<<endl;
    return 0;
}
### Prompt

Please create a solution in CPP 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>
using namespace std;
typedef long long ll;
const int N=2e5+10;
vector<pair<int,int> >v;
int ans[N],a[N];
int main()
{
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)ans[i]=1;
    for(i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end());
    memset(a,0,sizeof a);
    for(auto x:v)
    {
        int y=x.second;
        ans[y]=ans[y+1]=ans[y]+ans[y+1]-a[y];
        a[y]=ans[y];
    }
    cout<<ans[1];
    for(i=2;i<=n;i++)printf(" %d",ans[i]);
    cout<<endl;
    return 0;
}
```