#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	
	vector<pair<int,int> > arm(m);
	for(int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		arm[i]=make_pair(x,y);
	}
	sort(arm.begin(), arm.end());
	
	vector<int> ub(n+1), lb(n+1);
	for(int i=0; i<=n; i++){
		ub[i] = lb[i] = i;
	}
	for(int i=0; i<m; i++){
		int lane = arm[i].second;
		ub[lane] = ub[lane+1];
		lb[lane+1] = lb[lane];
	}
	
	for(int i=1; i<n; i++){
		cout << ub[i]-lb[i]+1 << " ";
	}
	cout << ub[n]-lb[n]+1 << endl;
	
	return 0;
}
### Prompt

Generate 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 <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main(){
	int n,m;
	cin >> n >> m;
	
	vector<pair<int,int> > arm(m);
	for(int i=0; i<m; i++){
		int x,y;
		cin >> x >> y;
		arm[i]=make_pair(x,y);
	}
	sort(arm.begin(), arm.end());
	
	vector<int> ub(n+1), lb(n+1);
	for(int i=0; i<=n; i++){
		ub[i] = lb[i] = i;
	}
	for(int i=0; i<m; i++){
		int lane = arm[i].second;
		ub[lane] = ub[lane+1];
		lb[lane+1] = lb[lane];
	}
	
	for(int i=1; i<n; i++){
		cout << ub[i]-lb[i]+1 << " ";
	}
	cout << ub[n]-lb[n]+1 << endl;
	
	return 0;
}
```