#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=200010, M=100010;
int n,m;
int ff[N],have[N];

struct edges{
	int x,y;
}e[M];

int cmp(edges a,edges b){
	return a.x<b.x;
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1; i<=m; ++i){
		scanf("%d%d",&x,&y);
		e[i] = (edges){x,y};
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1; i<=n; ++i) have[i] = 1;
	for(int i=1; i<=m; ++i){
		y = e[i].y;
		have[y] = have[y+1] = have[y]+have[y+1]-ff[y];
		ff[y] = have[y];
	}
	printf("%d",have[1]);
	for(int i=2; i<=n; ++i){
		printf(" %d",have[i]);
	}
	printf("\n");
	return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=200010, M=100010;
int n,m;
int ff[N],have[N];

struct edges{
	int x,y;
}e[M];

int cmp(edges a,edges b){
	return a.x<b.x;
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1; i<=m; ++i){
		scanf("%d%d",&x,&y);
		e[i] = (edges){x,y};
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1; i<=n; ++i) have[i] = 1;
	for(int i=1; i<=m; ++i){
		y = e[i].y;
		have[y] = have[y+1] = have[y]+have[y+1]-ff[y];
		ff[y] = have[y];
	}
	printf("%d",have[1]);
	for(int i=2; i<=n; ++i){
		printf(" %d",have[i]);
	}
	printf("\n");
	return 0;
}
```