#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 y,int t,int d){
	while(d){
		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;
		d&=d-1;
	}
}
int query(int y,int d){
	int X=2e9;
	for(;d<=s;d+=d&-d){
		auto it=v[d].upper_bound(y);
		if(it==v[d].begin())continue;
		X=min(X,(--it)->second);
	}
	return X;
}
int solve(int l,int r){
	int x=query(r,l);
	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){
		if(sta.size()&&h[i].empty()){sta.push(sta.top());continue;}
		for(auto j:h[i])ins(a[j].second,j,a[j].first);
		sta.push(solve(1,s));
	}while(sta.size())printf("%d\n",sta.top()),sta.pop();
	return 0;
}
