#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

typedef pair<int, int> P;

#define mind(a, b) (a < b ? a : b)
#define maxd(a, b) (a < b ? b : a)
#define N 200005

int dmin[N], dmax[N];

int n, m;
vector<P> ps;

int main() {
    cin >> n >> m;
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        ps.push_back(P(x, y));
    }
    sort(ps.begin(), ps.end());

    for(int i=0; i<n; ++i) {
        dmin[i] = dmax[i] = i;
    }

    for(int i=0; i<m; ++i) {
        P p = ps[i];
        int x = p.first, y = p.second;
        dmax[y-1] = dmax[y] = maxd(dmax[y-1], dmax[y]);
        dmin[y-1] = dmin[y] = mind(dmin[y-1], dmin[y]);
    }
    for(int i=0; i<n; ++i) {
        cout << (i ? " " : "") << (dmax[i] - dmin[i] + 1);
    }
    cout << endl;

    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 <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

typedef pair<int, int> P;

#define mind(a, b) (a < b ? a : b)
#define maxd(a, b) (a < b ? b : a)
#define N 200005

int dmin[N], dmax[N];

int n, m;
vector<P> ps;

int main() {
    cin >> n >> m;
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        ps.push_back(P(x, y));
    }
    sort(ps.begin(), ps.end());

    for(int i=0; i<n; ++i) {
        dmin[i] = dmax[i] = i;
    }

    for(int i=0; i<m; ++i) {
        P p = ps[i];
        int x = p.first, y = p.second;
        dmax[y-1] = dmax[y] = maxd(dmax[y-1], dmax[y]);
        dmin[y-1] = dmin[y] = mind(dmin[y-1], dmin[y]);
    }
    for(int i=0; i<n; ++i) {
        cout << (i ? " " : "") << (dmax[i] - dmin[i] + 1);
    }
    cout << endl;

    return 0;
}
```