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

using P = pair<int, int>;

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

    vector<P> xy(m);
    for (int i = 0; i < m; i++) {
        cin >> xy[i].first >> xy[i].second;
        xy[i].first--; xy[i].second--;
    }
    sort(xy.begin(), xy.end());

    vector<P> segment(n);
    for (int i = 0; i < n; i++) {
        segment[i] = make_pair(i, i);
    }
    for (int i = 0; i < m; i++) {
        int y = xy[i].second;
        segment[y].first = min(segment[y].first, segment[y+1].first);
        segment[y+1].first = min(segment[y].first, segment[y+1].first);

        segment[y].second = max(segment[y].second, segment[y+1].second);
        segment[y+1].second = max(segment[y].second, segment[y+1].second);

        /*
        cout << "y: " << y << " [" << segment[y].first << ", " << segment[y].second << "]" << endl;
        cout << "y+1: " << y+1 << " [" << segment[y+1].first << ", " << segment[y+1].second << "]" << endl;
        */
    }

    for (int i = 0; i < n; i++) {
        cout << (i == 0 ? "" : " ") << (segment[i].second - segment[i].first + 1);
    }
    cout << endl;

    return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

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

using P = pair<int, int>;

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

    vector<P> xy(m);
    for (int i = 0; i < m; i++) {
        cin >> xy[i].first >> xy[i].second;
        xy[i].first--; xy[i].second--;
    }
    sort(xy.begin(), xy.end());

    vector<P> segment(n);
    for (int i = 0; i < n; i++) {
        segment[i] = make_pair(i, i);
    }
    for (int i = 0; i < m; i++) {
        int y = xy[i].second;
        segment[y].first = min(segment[y].first, segment[y+1].first);
        segment[y+1].first = min(segment[y].first, segment[y+1].first);

        segment[y].second = max(segment[y].second, segment[y+1].second);
        segment[y+1].second = max(segment[y].second, segment[y+1].second);

        /*
        cout << "y: " << y << " [" << segment[y].first << ", " << segment[y].second << "]" << endl;
        cout << "y+1: " << y+1 << " [" << segment[y+1].first << ", " << segment[y+1].second << "]" << endl;
        */
    }

    for (int i = 0; i < n; i++) {
        cout << (i == 0 ? "" : " ") << (segment[i].second - segment[i].first + 1);
    }
    cout << endl;

    return 0;
}
```