#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    using P = pair<int, int>;
    vector<int> res(n, 1);
    vector<P> prev(n);
    vector<P> arms(m);
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        arms[i] = make_pair(x, y-1);
    }
    sort(arms.begin(), arms.end());
    for(int i=0; i<m; ++i) {
        int y = arms[i].second;
        int t1 = res[y] - prev[y].first, t2 = res[y+1] - prev[y].first;
        res[y] += t2;
        res[y+1] += t1;
        prev[y] = make_pair(res[y], res[y+1]);
    }
    for(int i=0; i<n; ++i) {
        cout << res[i] << " \n"[(i == n-1)];
    }
    cout << flush;
}

### Prompt

Generate 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;
    using P = pair<int, int>;
    vector<int> res(n, 1);
    vector<P> prev(n);
    vector<P> arms(m);
    for(int i=0; i<m; ++i) {
        int x, y;
        cin >> x >> y;
        arms[i] = make_pair(x, y-1);
    }
    sort(arms.begin(), arms.end());
    for(int i=0; i<m; ++i) {
        int y = arms[i].second;
        int t1 = res[y] - prev[y].first, t2 = res[y+1] - prev[y].first;
        res[y] += t2;
        res[y+1] += t1;
        prev[y] = make_pair(res[y], res[y+1]);
    }
    for(int i=0; i<n; ++i) {
        cout << res[i] << " \n"[(i == n-1)];
    }
    cout << flush;
}

```