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

#define pii pair<int, int>

using namespace std;

int main(void){
    int n, m;
    cin >> n >> m;
    vector<pii> v(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[i] = make_pair(a,b);
    }
    sort(v.begin(), v.end());
    
    vector<pii> vp(n);
    for (int i = 0; i < n; i++) vp[i].first = i, vp[i].second = i;
    
    for (int i = 0; i < m; i++) {
        int x = v[i].second;
        vp[x].first = vp[x-1].first;
        vp[x-1].second = vp[x].second;
    }
    for (int i = 0; i < n; i++) {
        cout << vp[i].second - vp[i].first + 1;
        if (i < n-1) cout << " ";
    }
    cout << endl;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

#define pii pair<int, int>

using namespace std;

int main(void){
    int n, m;
    cin >> n >> m;
    vector<pii> v(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[i] = make_pair(a,b);
    }
    sort(v.begin(), v.end());
    
    vector<pii> vp(n);
    for (int i = 0; i < n; i++) vp[i].first = i, vp[i].second = i;
    
    for (int i = 0; i < m; i++) {
        int x = v[i].second;
        vp[x].first = vp[x-1].first;
        vp[x-1].second = vp[x].second;
    }
    for (int i = 0; i < n; i++) {
        cout << vp[i].second - vp[i].first + 1;
        if (i < n-1) cout << " ";
    }
    cout << endl;
}
```