#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;

int n,m;
struct Node
{
    int x;
    int y;
}node[200005];
int l[200005],r[200005];

bool cmp(Node a,Node b)
{
    return a.x<b.x;
}

int main()
{
    scanf ("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf ("%d %d",&node[i].x,&node[i].y);
    sort(node+1,node+1+m,cmp);
    for (int i=1;i<=n;i++)
        l[i]=r[i]=i;
    for (int i=1;i<=m;i++)
        {
        l[node[i].y]=l[node[i].y+1]=min(l[node[i].y],l[node[i].y+1]);
        r[node[i].y]=r[node[i].y+1]=max(r[node[i].y],r[node[i].y+1]);
        }
    for (int i=1;i<n;i++)
        printf ("%d ",r[i]-l[i]+1);
    printf ("%d\n",r[n]-l[n]+1);
}
### 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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <algorithm>
using namespace std;

int n,m;
struct Node
{
    int x;
    int y;
}node[200005];
int l[200005],r[200005];

bool cmp(Node a,Node b)
{
    return a.x<b.x;
}

int main()
{
    scanf ("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf ("%d %d",&node[i].x,&node[i].y);
    sort(node+1,node+1+m,cmp);
    for (int i=1;i<=n;i++)
        l[i]=r[i]=i;
    for (int i=1;i<=m;i++)
        {
        l[node[i].y]=l[node[i].y+1]=min(l[node[i].y],l[node[i].y+1]);
        r[node[i].y]=r[node[i].y+1]=max(r[node[i].y],r[node[i].y+1]);
        }
    for (int i=1;i<n;i++)
        printf ("%d ",r[i]-l[i]+1);
    printf ("%d\n",r[n]-l[n]+1);
}
```