#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int INF = 1LL << 60;

constexpr int MAX_N = 200005;

typedef pair<int, int> pii;

int n, m, L[MAX_N], R[MAX_N];

vector<pii> rob;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fill(L, L + MAX_N, 1);
    fill(R, R + MAX_N, 1);

    cin >> n >> m;
    L[0] = R[0] = R[1] = L[n + 1] = 0;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        rob.emplace_back(x, y);
    }
    sort(rob.begin(), rob.end());

    for (const auto r : rob)
    {
        const int y = r.second;
        R[y + 2] += R[y + 1];
        R[y + 1] = 0;
        L[y] += L[y + 1];
        L[y + 1] = 0;
    }

//    for (int i = 1; i <= n + 1; i++)
//    {
//        cerr << i << ": " << L[i] << " " << R[i] << endl;
//    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += L[i] - R[i];
        cout << cnt;
        if (i != n) cout << " ";
    }
    cout << endl;
}


### Prompt

Please provide a Cpp coded solution to the problem described below:

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 int long long

constexpr int INF = 1LL << 60;

constexpr int MAX_N = 200005;

typedef pair<int, int> pii;

int n, m, L[MAX_N], R[MAX_N];

vector<pii> rob;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    fill(L, L + MAX_N, 1);
    fill(R, R + MAX_N, 1);

    cin >> n >> m;
    L[0] = R[0] = R[1] = L[n + 1] = 0;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        rob.emplace_back(x, y);
    }
    sort(rob.begin(), rob.end());

    for (const auto r : rob)
    {
        const int y = r.second;
        R[y + 2] += R[y + 1];
        R[y + 1] = 0;
        L[y] += L[y + 1];
        L[y + 1] = 0;
    }

//    for (int i = 1; i <= n + 1; i++)
//    {
//        cerr << i << ": " << L[i] << " " << R[i] << endl;
//    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt += L[i] - R[i];
        cout << cnt;
        if (i != n) cout << " ";
    }
    cout << endl;
}


```