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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int l[200005], r[200005];

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n, m; cin >> n >> m;

	vector<pii> v(m);
	rep(i, 0, m) cin >> v[i].first >> v[i].second;
	rep(i, 1, n + 1) l[i] = r[i] = i;
	sort(all(v));
	rep(i, 0, m) {
		int p = v[i].second;
		int nl = l[p], nr = r[p + 1];
		r[p] = nr; l[p + 1] = nl;
	}

	rep(i, 1, n + 1) {
		cout << (r[i] - l[i] + 1) << " \n"[i == n];
	}
}


### 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 <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int l[200005], r[200005];

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n, m; cin >> n >> m;

	vector<pii> v(m);
	rep(i, 0, m) cin >> v[i].first >> v[i].second;
	rep(i, 1, n + 1) l[i] = r[i] = i;
	sort(all(v));
	rep(i, 0, m) {
		int p = v[i].second;
		int nl = l[p], nr = r[p + 1];
		r[p] = nr; l[p + 1] = nl;
	}

	rep(i, 1, n + 1) {
		cout << (r[i] - l[i] + 1) << " \n"[i == n];
	}
}


```