#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int L[210000], R[210000];

int main(){
	int n, m;
	cin >> n >> m;
	vector<P> v;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		v.push_back(P(x, y));
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= n; i++){
		L[i] = R[i] = i;
	}
	for(P p : v){
		int y = p.second;
		R[y] = max(R[y], R[y + 1]);
		L[y + 1] = min(L[y + 1], L[y]);
	}
	for(int i = 1; i < n; i++){
		cout << R[i] - L[i] + 1 << " ";
	}
	cout << R[n] - L[n] + 1 << 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
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int L[210000], R[210000];

int main(){
	int n, m;
	cin >> n >> m;
	vector<P> v;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		v.push_back(P(x, y));
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= n; i++){
		L[i] = R[i] = i;
	}
	for(P p : v){
		int y = p.second;
		R[y] = max(R[y], R[y + 1]);
		L[y + 1] = min(L[y + 1], L[y]);
	}
	for(int i = 1; i < n; i++){
		cout << R[i] - L[i] + 1 << " ";
	}
	cout << R[n] - L[n] + 1 << endl;
	return 0;
}


```