#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using P = pair<ll, ll>;

void merge(vector<int> &a, vector<int> &b){
    if(a.size() < b.size()){
        swap(a, b);
    }
    for(auto &e : b){
        a.emplace_back(e);
    }
    b.clear();
}

int solve(){
    int n, m;
    cin >> n >> m;
    vector<P> arms(m);
    for(int i=0;i<m;i++){
        int x, y;
        cin >> x >> y;
        arms[i] = P(x,y-1);
    }
    sort(arms.rbegin(),arms.rend());
    vector<vector<int> > l(n), r(n);
    for(int i=0;i<n;i++){
        l[i].emplace_back(i);
        r[i].emplace_back(i);
    }
    for(auto p : arms){
        int i = p.second;
        merge(l[i], l[i+1]);
        merge(r[i+1], r[i]);
    }
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        for(auto j : r[i]){
            ans[j] += i+1;
        }
        for(auto j : l[i]){
            ans[j] -= i;
        }
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << " \n"[i==n-1];
    }
    return 0;
}


int main(){
    solve();
    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 <bits/stdc++.h>
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using P = pair<ll, ll>;

void merge(vector<int> &a, vector<int> &b){
    if(a.size() < b.size()){
        swap(a, b);
    }
    for(auto &e : b){
        a.emplace_back(e);
    }
    b.clear();
}

int solve(){
    int n, m;
    cin >> n >> m;
    vector<P> arms(m);
    for(int i=0;i<m;i++){
        int x, y;
        cin >> x >> y;
        arms[i] = P(x,y-1);
    }
    sort(arms.rbegin(),arms.rend());
    vector<vector<int> > l(n), r(n);
    for(int i=0;i<n;i++){
        l[i].emplace_back(i);
        r[i].emplace_back(i);
    }
    for(auto p : arms){
        int i = p.second;
        merge(l[i], l[i+1]);
        merge(r[i+1], r[i]);
    }
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        for(auto j : r[i]){
            ans[j] += i+1;
        }
        for(auto j : l[i]){
            ans[j] -= i;
        }
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << " \n"[i==n-1];
    }
    return 0;
}


int main(){
    solve();
    return 0;
}


```