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

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pii> v(n);
    REP (i, 0, n) v[i].first = v[i].second = i;
    vector<pii> p(m);
    REP (i, 0, m) {
        cin >> p[i].first >> p[i].second;
    }
    sort(begin(p), end(p));
    REP (i, 0, m) {
        int y = p[i].second - 1;
        v[y + 1].first = v[y].first;
        v[y].second = v[y + 1].second;
    }
    REP (i, 0, n) {
        cout << v[i].second - v[i].first + 1 << " \n"[i == n - 1];
    }
    return 0;
}

### 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>
#include <string>
#include <utility>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

int main() {
    int n, m;
    cin >> n >> m;
    vector<pii> v(n);
    REP (i, 0, n) v[i].first = v[i].second = i;
    vector<pii> p(m);
    REP (i, 0, m) {
        cin >> p[i].first >> p[i].second;
    }
    sort(begin(p), end(p));
    REP (i, 0, m) {
        int y = p[i].second - 1;
        v[y + 1].first = v[y].first;
        v[y].second = v[y + 1].second;
    }
    REP (i, 0, n) {
        cout << v[i].second - v[i].first + 1 << " \n"[i == n - 1];
    }
    return 0;
}

```