#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> arms(m);
    for (auto &p: arms) cin >> p.first >> p.second;
    sort(arms.begin(), arms.end());
    vector<pair<int, int>> seg(n);
    for (int i = 0; i < n; i++) seg[i] = {i + 1, i + 1};
    for (auto &p: arms) {
        int a = p.second - 1, b = p.second;
        seg[a].second = seg[b].second;
        seg[b].first = seg[a].first;
    }
    for (int i = 0; i < n; i++) {
        int s, t; tie(s, t) = seg[i];
        cout << (t - s + 1) << " \n"[i == n - 1];
    }
    return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> arms(m);
    for (auto &p: arms) cin >> p.first >> p.second;
    sort(arms.begin(), arms.end());
    vector<pair<int, int>> seg(n);
    for (int i = 0; i < n; i++) seg[i] = {i + 1, i + 1};
    for (auto &p: arms) {
        int a = p.second - 1, b = p.second;
        seg[a].second = seg[b].second;
        seg[b].first = seg[a].first;
    }
    for (int i = 0; i < n; i++) {
        int s, t; tie(s, t) = seg[i];
        cout << (t - s + 1) << " \n"[i == n - 1];
    }
    return 0;
}

```