#include "bits/stdc++.h"
using namespace std;
/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1369
??????????????????

???ICPC??\??´?????????????????£???????????¨????????°?????????????????????????????????????????°???????????????????????¢???
????£??????????????????????????????§???????????¶?????????????????????????????????????????????????????????????????????????????¢??????
???????°???\???????????????1????????????????????????????????????????§??????§??????????????????????????¢???????¨?????????????
????????????????????°???????£??????????????????????????????¨??????????????¨????¨±?????????????????°???????????????

?????????????????¢???????????????????????????, ????£???????????????????????????????????????????????????????????????°?????????
??????????????????????????????????????¨?????°??????????????????????£?????????????????????\????????????????????¨?¢???????????????¨??????
??????????????¢?????°????????????????????¢??????????????????????????£??????????????????
*/
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<int> line(200000, 0);
	vector<int> min_line(n, 0), max_line(n, 0); // min~max_line[i] = i????????????????????°?????§??????????????????or???????????????
	for (int i = 0; i < m;i++) {
		int x, y; cin >> x >> y;
		line[x] = y;
	}
	for (int i = 0; i < n;i++) {
		min_line[i] = max_line[i] = i;
	}
	for (int i = 0; i < 200000;i++) {
		if (line[i] == 0)continue;
		min_line[line[i] - 1] = min_line[line[i]] = min(min_line[line[i] - 1], min_line[line[i]]);
		max_line[line[i] - 1] = max_line[line[i]] = max(max_line[line[i] - 1], max_line[line[i]]);
	}
	cout << max_line[0] - min_line[0] + 1;
	for (int i = 1; i < n;i++) {
		cout << " " << max_line[i] - min_line[i] + 1;
	}
	cout << endl;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include "bits/stdc++.h"
using namespace std;
/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1369
??????????????????

???ICPC??\??´?????????????????£???????????¨????????°?????????????????????????????????????????°???????????????????????¢???
????£??????????????????????????????§???????????¶?????????????????????????????????????????????????????????????????????????????¢??????
???????°???\???????????????1????????????????????????????????????????§??????§??????????????????????????¢???????¨?????????????
????????????????????°???????£??????????????????????????????¨??????????????¨????¨±?????????????????°???????????????

?????????????????¢???????????????????????????, ????£???????????????????????????????????????????????????????????????°?????????
??????????????????????????????????????¨?????°??????????????????????£?????????????????????\????????????????????¨?¢???????????????¨??????
??????????????¢?????°????????????????????¢??????????????????????????£??????????????????
*/
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<int> line(200000, 0);
	vector<int> min_line(n, 0), max_line(n, 0); // min~max_line[i] = i????????????????????°?????§??????????????????or???????????????
	for (int i = 0; i < m;i++) {
		int x, y; cin >> x >> y;
		line[x] = y;
	}
	for (int i = 0; i < n;i++) {
		min_line[i] = max_line[i] = i;
	}
	for (int i = 0; i < 200000;i++) {
		if (line[i] == 0)continue;
		min_line[line[i] - 1] = min_line[line[i]] = min(min_line[line[i] - 1], min_line[line[i]]);
		max_line[line[i] - 1] = max_line[line[i]] = max(max_line[line[i] - 1], max_line[line[i]]);
	}
	cout << max_line[0] - min_line[0] + 1;
	for (int i = 1; i < n;i++) {
		cout << " " << max_line[i] - min_line[i] + 1;
	}
	cout << endl;
}
```