#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;

P s[100000], p[200000];
int main() {
	int n, m; scanf("%d%d", &n, &m);
	rep(i, m)scanf("%d%d", &s[i].first, &s[i].second);
	rep(i, n)p[i] = { i,i };
	sort(s, s + m);
	rep(i, m) {
		int a = min(p[s[i].second - 1].first, p[s[i].second].first);
		int b = max(p[s[i].second - 1].second, p[s[i].second].second);
		p[s[i].second - 1] = p[s[i].second] = { a,b };
	}
	rep(i, n) {
		if (i)printf(" ");
		printf("%d", p[i].second - p[i].first + 1);
	}
	printf("\n");
}
### Prompt

Your task is to create a cpp solution to 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 rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;

P s[100000], p[200000];
int main() {
	int n, m; scanf("%d%d", &n, &m);
	rep(i, m)scanf("%d%d", &s[i].first, &s[i].second);
	rep(i, n)p[i] = { i,i };
	sort(s, s + m);
	rep(i, m) {
		int a = min(p[s[i].second - 1].first, p[s[i].second].first);
		int b = max(p[s[i].second - 1].second, p[s[i].second].second);
		p[s[i].second - 1] = p[s[i].second] = { a,b };
	}
	rep(i, n) {
		if (i)printf(" ");
		printf("%d", p[i].second - p[i].first + 1);
	}
	printf("\n");
}
```