#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
typedef pair<int,int> pii;

int main(){
	int n, m;
	vector<pii> v;
	cin >> n >> m;
	rep(i,m){
		int x, y;
		cin >> x >> y;
		y--;
		v.emplace_back(x, y);
	}
	sort(v.begin(), v.end());

	vector<pii> ans(n);
	rep(i,n) ans[i] = pii(i,i+1);
	for(auto p: v){
		int y = p.second;
		ans[y+0].second = ans[y+1].second;
		ans[y+1].first  = ans[y+0].first;
	}

	rep(i,n){
		cout << ans[i].second-ans[i].first;
		if( i < n-1 ) cout << " ";
	}
	cout << endl;

	return 0;
}
### 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 <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
typedef pair<int,int> pii;

int main(){
	int n, m;
	vector<pii> v;
	cin >> n >> m;
	rep(i,m){
		int x, y;
		cin >> x >> y;
		y--;
		v.emplace_back(x, y);
	}
	sort(v.begin(), v.end());

	vector<pii> ans(n);
	rep(i,n) ans[i] = pii(i,i+1);
	for(auto p: v){
		int y = p.second;
		ans[y+0].second = ans[y+1].second;
		ans[y+1].first  = ans[y+0].first;
	}

	rep(i,n){
		cout << ans[i].second-ans[i].first;
		if( i < n-1 ) cout << " ";
	}
	cout << endl;

	return 0;
}
```