#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>

using namespace std;

using lint = long long;
using ldouble = long double;

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> arms(m);
    for (auto& a : arms) {
        cin >> a.first >> a.second;
        --a.second;
    }
    sort(arms.begin(), arms.end());

    vector<int> l(n), r(n);
    iota(l.begin(), l.end(), 0);
    iota(r.begin(), r.end(), 0);

    for (auto a : arms) {
        int x = a.second, y = a.second + 1;
        l[y] = l[x];
        r[x] = r[y];
    }

    for (int i = 0; i < n; ++i) {
        cout << r[i] - l[i] + 1 << " \n"[i == n - 1];
    }
    return 0;
}


### Prompt

Please formulate 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 <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>

using namespace std;

using lint = long long;
using ldouble = long double;

int main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> arms(m);
    for (auto& a : arms) {
        cin >> a.first >> a.second;
        --a.second;
    }
    sort(arms.begin(), arms.end());

    vector<int> l(n), r(n);
    iota(l.begin(), l.end(), 0);
    iota(r.begin(), r.end(), 0);

    for (auto a : arms) {
        int x = a.second, y = a.second + 1;
        l[y] = l[x];
        r[x] = r[y];
    }

    for (int i = 0; i < n; ++i) {
        cout << r[i] - l[i] + 1 << " \n"[i == n - 1];
    }
    return 0;
}


```