#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
int s,m;
pair<int,int>a[100005];
vector<int>h[50005];
map<int,int>v[200005];
void ins(int x,int y,int t,int l,int r,int d){
//	cout<<l<<' '<<r<<' '<<t<<endl;
	auto it=v[d].lower_bound(y);
	while(it!=v[d].end()&&it->second>t){
		v[d].erase(it);
		it=v[d].lower_bound(y);
	}it=v[d].upper_bound(y);
	if(it==v[d].begin()||(--it)->second>=t)v[d][y]=t;
	if(l==r)return;
	int mid=l+r>>1;
	if(x<=mid)ins(x,y,t,l,mid,d<<1);
	else ins(x,y,t,mid+1,r,d<<1|1); 
}
int query(int x,int y,int l,int r,int d){
	if(x>r||v[d].empty())return 2e9;
	if(x<=l){
		auto it=v[d].upper_bound(y);
		if(it==v[d].begin())return 2e9;
		return (--it)->second;
	}int mid=l+r>>1;
	return min(query(x,y,l,mid,d<<1),query(x,y,mid+1,r,d<<1|1));
}
int solve(int l,int r){
	int x=query(l,r,1,s,1);
//	cout<<"::"<<x<<endl;
	if(x==2e9)return 0;
	return solve(l,a[x].first-1)+solve(a[x].second+1,r)+a[x].second-a[x].first+1;
}stack<int>sta;
int main(){
	s=read,m=read;
	for(int i=1;i<=m;++i)a[i].first=read,a[i].second=read,h[a[i].second-a[i].first+1].push_back(i);
	for(int i=s;i;--i){
		for(auto j:h[i])ins(a[j].first,a[j].second,j,1,s,1);
		sta.push(solve(1,s));
	}while(sta.size())printf("%d\n",sta.top()),sta.pop();
	return 0;
}
