#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
using namespace std;
const int maxn=200000+5;
int n,m,a[maxn];
vector<int>l[maxn],r[maxn];
map<int,int>edl[maxn],edr[maxn];
int gor(int now,int j){
	if(r[j].empty())return j;
	auto it=upper_bound(r[j].begin(),r[j].end(),now);
	if(it==r[j].begin())return j;
	it--;now=*it;
	if(edr[j].count(now))return edr[j][now];
	return edr[j][now]=gor(now,j+1);
}
int gol(int now,int j){
	if(l[j].empty())return j;
	auto it=upper_bound(l[j].begin(),l[j].end(),now);
	if(it==l[j].begin())return j;
	it--;now=*it;
	if(edl[j].count(now))return edl[j][now];
	return edl[j][now]=gol(now,j-1);
}
int main(){
    scanf("%d%d",&n,&m);
	int x,y;
	rep(i,1,m)scanf("%d%d",&x,&y),r[y].push_back(x),l[y+1].push_back(x);
	rep(i,1,n)sort(l[i].begin(),l[i].end()),sort(r[i].begin(),r[i].end());
	rep(i,1,n){
		int j;a[i]++;
		j=gor(1e9,i);
		a[i]+=j-i;
		j=gol(1e9,i);
		a[i]+=i-j;
	}
	rep(i,1,n-1)printf("%d ",a[i]);
	printf("%d\n",a[n]);
	return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
using namespace std;
const int maxn=200000+5;
int n,m,a[maxn];
vector<int>l[maxn],r[maxn];
map<int,int>edl[maxn],edr[maxn];
int gor(int now,int j){
	if(r[j].empty())return j;
	auto it=upper_bound(r[j].begin(),r[j].end(),now);
	if(it==r[j].begin())return j;
	it--;now=*it;
	if(edr[j].count(now))return edr[j][now];
	return edr[j][now]=gor(now,j+1);
}
int gol(int now,int j){
	if(l[j].empty())return j;
	auto it=upper_bound(l[j].begin(),l[j].end(),now);
	if(it==l[j].begin())return j;
	it--;now=*it;
	if(edl[j].count(now))return edl[j][now];
	return edl[j][now]=gol(now,j-1);
}
int main(){
    scanf("%d%d",&n,&m);
	int x,y;
	rep(i,1,m)scanf("%d%d",&x,&y),r[y].push_back(x),l[y+1].push_back(x);
	rep(i,1,n)sort(l[i].begin(),l[i].end()),sort(r[i].begin(),r[i].end());
	rep(i,1,n){
		int j;a[i]++;
		j=gor(1e9,i);
		a[i]+=j-i;
		j=gol(1e9,i);
		a[i]+=i-j;
	}
	rep(i,1,n-1)printf("%d ",a[i]);
	printf("%d\n",a[n]);
	return 0;
}

```