#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <time.h>
#include <set>
#include <queue>
#define scan(a) scanf("%d",&a)
#define scann(n,m) scanf("%d%d",&n,&m)
#define scannn(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define print(a) printf("%d\n",a)
#define dg(x) cout<<#x<<"="<<x<<endl
#define mem(a,n) memset(a,n,sizeof(a))
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
typedef pair<int,int> PP;
typedef long long ll;
typedef unsigned long long ull;
ll powmod(ll a,ll x,ll mod){ll t=1ll;while(x){if(x&1)t=t*a%mod;a=a*a%mod;x>>=1;}return t;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
//==============================================================================================
int n,m;
int dp[maxn],f[maxn];
struct node{
    int x,y;
}p[maxn];

bool cmp(node a,node b){
    return a.x<b.x;
}

int main()
{
    //freopen("F://Duipai//in.txt","r",stdin);
    //freopen("F://Duipai//out.txt","w",stdout);

    while(~scann(n,m)){
        for(int i=0;i<m;i++)
            scann(p[i].x,p[i].y);
        sort(p,p+m,cmp);
        for(int i=1;i<=n;i++) dp[i]=1,f[i]=1;

        for(int i=0;i<m;i++){
            int yy=p[i].y;
            dp[yy+1]=dp[yy]+1;
        }

        for(int i=0;i<m;i++){
            int yy=p[i].y;
            f[yy]=f[yy+1]+1;
        }

        for(int i=1;i<=n;i++)
            printf("%d%c",dp[i]+f[i]-1,i==n?'\n':' ');
    }
    return 0;
}
### Prompt

Your challenge is to write 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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <time.h>
#include <set>
#include <queue>
#define scan(a) scanf("%d",&a)
#define scann(n,m) scanf("%d%d",&n,&m)
#define scannn(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define print(a) printf("%d\n",a)
#define dg(x) cout<<#x<<"="<<x<<endl
#define mem(a,n) memset(a,n,sizeof(a))
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
typedef pair<int,int> PP;
typedef long long ll;
typedef unsigned long long ull;
ll powmod(ll a,ll x,ll mod){ll t=1ll;while(x){if(x&1)t=t*a%mod;a=a*a%mod;x>>=1;}return t;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
//==============================================================================================
int n,m;
int dp[maxn],f[maxn];
struct node{
    int x,y;
}p[maxn];

bool cmp(node a,node b){
    return a.x<b.x;
}

int main()
{
    //freopen("F://Duipai//in.txt","r",stdin);
    //freopen("F://Duipai//out.txt","w",stdout);

    while(~scann(n,m)){
        for(int i=0;i<m;i++)
            scann(p[i].x,p[i].y);
        sort(p,p+m,cmp);
        for(int i=1;i<=n;i++) dp[i]=1,f[i]=1;

        for(int i=0;i<m;i++){
            int yy=p[i].y;
            dp[yy+1]=dp[yy]+1;
        }

        for(int i=0;i<m;i++){
            int yy=p[i].y;
            f[yy]=f[yy+1]+1;
        }

        for(int i=1;i<=n;i++)
            printf("%d%c",dp[i]+f[i]-1,i==n?'\n':' ');
    }
    return 0;
}
```