#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
} a[100005];
//int ans[200005];
int l[200005],r[200005];
int main ()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1; i<=n; i++)
        l[i]=r[i]=i;
    sort(a,a+m,[](node xx,node yy)
    {
        return xx.x<yy.x;
    });
    for(int i=0;i<m;i++)
    {
        l[a[i].y+1]=min(l[a[i].y],l[a[i].y+1]);
        r[a[i].y]=max(r[a[i].y],r[a[i].y+1]);
    }
    printf("%d",r[1]-l[1]+1);
    for(int i=2;i<=n;i++)
        printf(" %d",r[i]-l[i]+1);
    puts("");
}
### Prompt

Develop a solution in Cpp to the problem described below:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int x,y;
} a[100005];
//int ans[200005];
int l[200005],r[200005];
int main ()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1; i<=n; i++)
        l[i]=r[i]=i;
    sort(a,a+m,[](node xx,node yy)
    {
        return xx.x<yy.x;
    });
    for(int i=0;i<m;i++)
    {
        l[a[i].y+1]=min(l[a[i].y],l[a[i].y+1]);
        r[a[i].y]=max(r[a[i].y],r[a[i].y+1]);
    }
    printf("%d",r[1]-l[1]+1);
    for(int i=2;i<=n;i++)
        printf(" %d",r[i]-l[i]+1);
    puts("");
}
```