#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 200005

using namespace std;

int n,m,ans[maxn][3];
struct node
{
    int x,y;
    bool operator <(const node &a)const
    {
        return x<a.x;
    }
}d[maxn/2];

int main()
{

    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d%d",&d[i].x,&d[i].y);
    sort(d,d+m);
    for (int i=1;i<=n;i++) ans[i][1]=1;
    for (int i=0;i<m;i++)
    {
      
        int p=d[i].y,t1=ans[p][1],t2=ans[p+1][1];
        ans[p][1]+=t2-ans[p][2];
        ans[p+1][1]+=t1-ans[p+1][0];

        ans[p][2]=ans[p+1][1];
        ans[p+1][0]=ans[p][1];
    }
    for (int i=1;i<n;i++) printf("%d ",ans[i][1]);
    printf("%d\n",ans[n][1]);
    return 0;
}
### Prompt

Generate 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 <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 200005

using namespace std;

int n,m,ans[maxn][3];
struct node
{
    int x,y;
    bool operator <(const node &a)const
    {
        return x<a.x;
    }
}d[maxn/2];

int main()
{

    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d%d",&d[i].x,&d[i].y);
    sort(d,d+m);
    for (int i=1;i<=n;i++) ans[i][1]=1;
    for (int i=0;i<m;i++)
    {
      
        int p=d[i].y,t1=ans[p][1],t2=ans[p+1][1];
        ans[p][1]+=t2-ans[p][2];
        ans[p+1][1]+=t1-ans[p+1][0];

        ans[p][2]=ans[p+1][1];
        ans[p+1][0]=ans[p][1];
    }
    for (int i=1;i<n;i++) printf("%d ",ans[i][1]);
    printf("%d\n",ans[n][1]);
    return 0;
}
```