#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long

using namespace std;
struct Arm
{
    int x,y;
    bool operator <  (const Arm & rhs) const{
        return x<rhs.x;
    }
}arm[100010];
int n,m;
int dp[200020][2];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        dp[i][2]=dp[i][1]=i;

    for(int i=1;i<=m;i++){
        scanf("%d%d",&arm[i].x,&arm[i].y);
    }
    sort(arm+1,arm+1+m);
    for(int i=1;i<=m;i++){
            int y=arm[i].y;
            dp[y][2]=dp[y+1][2];
            dp[y+1][1]=dp[y][1];
    }
    for(int i=1;i<=n;i++)
        if(i!=n)
            printf("%d ",dp[i][2]-dp[i][1]+1);
        else
            printf("%d\n",dp[i][2]-dp[i][1]+1);
    return 0;
}
### Prompt

In cpp, your task is to solve 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 LL long long
#define ULL unsigned long long

using namespace std;
struct Arm
{
    int x,y;
    bool operator <  (const Arm & rhs) const{
        return x<rhs.x;
    }
}arm[100010];
int n,m;
int dp[200020][2];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        dp[i][2]=dp[i][1]=i;

    for(int i=1;i<=m;i++){
        scanf("%d%d",&arm[i].x,&arm[i].y);
    }
    sort(arm+1,arm+1+m);
    for(int i=1;i<=m;i++){
            int y=arm[i].y;
            dp[y][2]=dp[y+1][2];
            dp[y+1][1]=dp[y][1];
    }
    for(int i=1;i<=n;i++)
        if(i!=n)
            printf("%d ",dp[i][2]-dp[i][1]+1);
        else
            printf("%d\n",dp[i][2]-dp[i][1]+1);
    return 0;
}
```