#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<pair<int, int>> a(m);

    for(int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a.begin(), a.end());

    vector<pair<int, int>> b(n);

    for(int i = 0; i < n; i++) {
        b[i].first = b[i].second = i;
    }

    for(int i = 0; i < m; i++) {
        int y = a[i].second - 1;

        b[y].second = b[y + 1].second;
        b[y + 1].first = b[y].first;
    }

    for(int i = 0; i < n; i++) {
        cout << b[i].second - b[i].first + 1 << " \n"[i + 1 == n];
    }
}

### 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 <vector>
#include <algorithm>

using namespace std;

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

    vector<pair<int, int>> a(m);

    for(int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a.begin(), a.end());

    vector<pair<int, int>> b(n);

    for(int i = 0; i < n; i++) {
        b[i].first = b[i].second = i;
    }

    for(int i = 0; i < m; i++) {
        int y = a[i].second - 1;

        b[y].second = b[y + 1].second;
        b[y + 1].first = b[y].first;
    }

    for(int i = 0; i < n; i++) {
        cout << b[i].second - b[i].first + 1 << " \n"[i + 1 == n];
    }
}

```