#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> xy(m);
	for (int i = 0; i < m; i++) {
		cin >> xy[i].first >> xy[i].second;
	}
	sort(xy.begin(), xy.end());
	vector<vector<int>> dp(n, vector<int>(2, 1));
	for (int i = 0; i < n; i++) {
		dp[i][0] = dp[i][1] = i;
	}
	for (int i = 0; i < m; i++) {
		int v = xy[i].second;
		dp[v][0] = dp[v - 1][0];
		dp[v - 1][1] = dp[v][1];
	}
	for (int i = 0; i < n; i++) {
		cout << (dp[i][1] - dp[i][0] + 1) << " \n"[i == n - 1];
	}
	return 0;
}
### Prompt

In Cpp, your task is to solve 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()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> xy(m);
	for (int i = 0; i < m; i++) {
		cin >> xy[i].first >> xy[i].second;
	}
	sort(xy.begin(), xy.end());
	vector<vector<int>> dp(n, vector<int>(2, 1));
	for (int i = 0; i < n; i++) {
		dp[i][0] = dp[i][1] = i;
	}
	for (int i = 0; i < m; i++) {
		int v = xy[i].second;
		dp[v][0] = dp[v - 1][0];
		dp[v - 1][1] = dp[v][1];
	}
	for (int i = 0; i < n; i++) {
		cout << (dp[i][1] - dp[i][0] + 1) << " \n"[i == n - 1];
	}
	return 0;
}
```