#include <bits/stdc++.h>

using namespace std;

int main(){
	long long int n,m;
	cin>>n>>m;
	vector<set<int>>VSI(n);
	vector<int>imosmax(n), imosmin(n);
	for(int i = 0; i < n; i++){
		VSI[i].insert(i);
		imosmax[i] = 1;
		imosmin[i] = 1;
	}
	vector<pair<long long int, long long int>>xy(m);
	for(int i = 0; i < m; i++){
		cin >> xy[i].first >> xy[i].second;
	}
	sort(xy.begin(), xy.end());
	for(int i = 0; i < m; i++){
		int y = xy[i].second;
		imosmax[y] += imosmax[y-1];
		imosmax[y-1] = 0;
		imosmin[y-1] += imosmin[y];
		imosmin[y] = 0;
	}
	vector<int>imos(n+1);
	
	for(int i = 0; i < n; i++){
		imos[i] += imosmin[i];
		imos[i+1] += imos[i];
		imos[i+1] -= imosmax[i];
		cout << imos[i] << (i==n-1?"\n":" ");
	}
}
### Prompt

Please formulate 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>

using namespace std;

int main(){
	long long int n,m;
	cin>>n>>m;
	vector<set<int>>VSI(n);
	vector<int>imosmax(n), imosmin(n);
	for(int i = 0; i < n; i++){
		VSI[i].insert(i);
		imosmax[i] = 1;
		imosmin[i] = 1;
	}
	vector<pair<long long int, long long int>>xy(m);
	for(int i = 0; i < m; i++){
		cin >> xy[i].first >> xy[i].second;
	}
	sort(xy.begin(), xy.end());
	for(int i = 0; i < m; i++){
		int y = xy[i].second;
		imosmax[y] += imosmax[y-1];
		imosmax[y-1] = 0;
		imosmin[y-1] += imosmin[y];
		imosmin[y] = 0;
	}
	vector<int>imos(n+1);
	
	for(int i = 0; i < n; i++){
		imos[i] += imosmin[i];
		imos[i+1] += imos[i];
		imos[i+1] -= imosmax[i];
		cout << imos[i] << (i==n-1?"\n":" ");
	}
}
```