#include<bits/stdc++.h>
#define ll long long
#define MAX  2147483647
#define fi first
#define se second
#define mid (l+r>>1)
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fodown(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int n,m;
pair<int,int> num[200001];
struct node{
	int x,y;
}a[100001];
int read()
{
   int x=0,tmp=1;
   char ch=getchar();
   while(ch<'0' || ch>'9' ) { if(ch=='-') tmp=-1;ch=getchar();}
   while(ch>='0'&& ch<='9') { x = x * 10+ ch-'0';ch=getchar();}
   return x*tmp;
}
int cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
  // freopen(" .in","r",stdin);
  // freopen(" .out","w",stdout);
  n=read();
  m=read();
  fo(i,1,m)
  {
  	 a[i].x=read();
  	 a[i].y=read();
  }
  sort(a+1,a+m+1,cmp);
  fo(i,1,n)
  num[i].fi=i,num[i].se=i;
  int y;
  for(int i=1;i<=m;i++){
  	    y= a[i].y;
        num[y].fi = num[y+1].fi = min(num[y].fi, num[y+1].fi);
        num[y].se = num[y+1].se = max(num[y].se, num[y+1].se);
  }
  fo(i,1,n-1)
  {
    printf("%d ",num[i].se-num[i].fi+1);	
  }
  cout<<num[n].se-num[n].fi+1<<endl;
   return 0;
}
### Prompt

Create a solution in cpp for 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 MAX  2147483647
#define fi first
#define se second
#define mid (l+r>>1)
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fodown(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int n,m;
pair<int,int> num[200001];
struct node{
	int x,y;
}a[100001];
int read()
{
   int x=0,tmp=1;
   char ch=getchar();
   while(ch<'0' || ch>'9' ) { if(ch=='-') tmp=-1;ch=getchar();}
   while(ch>='0'&& ch<='9') { x = x * 10+ ch-'0';ch=getchar();}
   return x*tmp;
}
int cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
  // freopen(" .in","r",stdin);
  // freopen(" .out","w",stdout);
  n=read();
  m=read();
  fo(i,1,m)
  {
  	 a[i].x=read();
  	 a[i].y=read();
  }
  sort(a+1,a+m+1,cmp);
  fo(i,1,n)
  num[i].fi=i,num[i].se=i;
  int y;
  for(int i=1;i<=m;i++){
  	    y= a[i].y;
        num[y].fi = num[y+1].fi = min(num[y].fi, num[y+1].fi);
        num[y].se = num[y+1].se = max(num[y].se, num[y+1].se);
  }
  fo(i,1,n-1)
  {
    printf("%d ",num[i].se-num[i].fi+1);	
  }
  cout<<num[n].se-num[n].fi+1<<endl;
   return 0;
}
```