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

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

vector<P> dp(200010);

int main(){
    int n, m; cin>>n>>m;
    vector<P> arm(m);
    for(int i=0; i<m; i++){
        int dist, id; cin>>dist>>id;
        arm[i]=P(dist, id);
    }
    sort(arm.begin(), arm.end());

    for(int i=1; i<=n; i++){
        dp[i]=P(i, i);
    }

    for(int i=0; i<m; i++){
        int dist, id;
        tie(dist, id)=arm[i];
        dp[id+1]=P(min(dp[id+1].first, dp[id].first), max(dp[id+1].second, dp[id].second));
        dp[id]=P(min(dp[id+1].first, dp[id].first), max(dp[id+1].second, dp[id].second));
    }

    for(int i=1; i<=n; i++){
        int dpmin, dpmax;
        tie(dpmin, dpmax)=dp[i];
        if(i==n) cout << dpmax-dpmin+1 << endl;
        else cout << dpmax-dpmin+1 << " ";
    }
}

### Prompt

Create a solution in cpp for 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;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

vector<P> dp(200010);

int main(){
    int n, m; cin>>n>>m;
    vector<P> arm(m);
    for(int i=0; i<m; i++){
        int dist, id; cin>>dist>>id;
        arm[i]=P(dist, id);
    }
    sort(arm.begin(), arm.end());

    for(int i=1; i<=n; i++){
        dp[i]=P(i, i);
    }

    for(int i=0; i<m; i++){
        int dist, id;
        tie(dist, id)=arm[i];
        dp[id+1]=P(min(dp[id+1].first, dp[id].first), max(dp[id+1].second, dp[id].second));
        dp[id]=P(min(dp[id+1].first, dp[id].first), max(dp[id+1].second, dp[id].second));
    }

    for(int i=1; i<=n; i++){
        int dpmin, dpmax;
        tie(dpmin, dpmax)=dp[i];
        if(i==n) cout << dpmax-dpmin+1 << endl;
        else cout << dpmax-dpmin+1 << " ";
    }
}

```