#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
#define eps 1e-9
#define SQ 225
LL read() {
	LL f = 1,x = 0;char s = getchar();
	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
	return f * x;
}
int n,m,i,j,s,o,k;
int ll[MAXN],rr[MAXN];
int b[MAXN];
bool cmp(int a,int b) {return rr[a]-ll[a] > rr[b]-ll[b];}
struct it{
	int x,y,mi,L,R,U,D,ii;
	int ls,rs;
	it(){x=y=0;mi=0x3f3f3f3f;L=D=0x3f3f3f3f,U=R=0;ls=rs=0;ii=0;}
	it(int X,int Y) {x=X;y=Y;}
}p[MAXN];
int root;
inline void update(int x,int a) {
	p[x].L = min(p[x].L,p[a].L);
	p[x].R = max(p[x].R,p[a].R);
	p[x].D = min(p[x].D,p[a].D);
	p[x].U = max(p[x].U,p[a].U);
	p[x].mi = min(p[x].mi,p[a].mi);
}
inline bool cmpx(it a,it b) {return a.x==b.x ? (a.y < b.y):(a.x < b.x);}
inline bool cmpy(it a,it b) {return a.y!=b.y ? (a.y < b.y):(a.x < b.x);}
inline int build(int l,int r,int op) {
	if(l > r) return 0;
	int mid = (l+r)>>1;
	if(op) nth_element(p + l,p + mid,p + r + 1,cmpx);
	else nth_element(p + l,p + mid,p + r + 1,cmpy);
	p[mid].ls = build(l,mid-1,op^1);
	p[mid].rs = build(mid+1,r,op^1);
	update(mid,p[mid].ls); update(mid,p[mid].rs);
	return mid;
}
inline void addplane(int a,int l,int r,int id,int op) {
//	printf("(%d,%d) = (%d,%d) ? \n",p[a].x,p[a].y,l,r);
	if(!a) return ;
	if(p[a].x == l && p[a].y == r) {
		p[a].mi = min(p[a].mi,id);
		p[a].ii = min(p[a].ii,id);
		return ;
	}
	if((op && cmpx(it(l,r),p[a])) || (!op && cmpy(it(l,r),p[a]))) {
		addplane(p[a].ls,l,r,id,op^1);
		p[a].mi = min(p[a].mi,p[p[a].ls].mi); return ;
	}
	addplane(p[a].rs,l,r,id,op^1);
	p[a].mi = min(p[a].mi,p[p[a].rs].mi); return ;
}
inline int findseg(int a,int l,int r,int rs) {
//	printf("[%d,%d][%d,%d] hs (%d,%d) ? \n",p[a].L,p[a].R,p[a].D,p[a].U,l,r);
	if(!a || p[a].mi >= rs || p[a].L > r || p[a].R < l || p[a].U < l || p[a].D > r) return rs;
	if(p[a].L>=l && p[a].R<=r && p[a].D>=l && p[a].U<=r) return p[a].mi;
	if(p[a].x >= l && p[a].y <= r) rs = min(rs,p[a].ii);
	if(p[p[a].ls].mi <= p[p[a].rs].mi) {
		rs = min(rs,findseg(p[a].ls,l,r,rs));
		return min(rs,findseg(p[a].rs,l,r,rs));
	}
	else {
		rs = min(rs,findseg(p[a].rs,l,r,rs));
		return min(rs,findseg(p[a].ls,l,r,rs));
	}
}
inline int solve(int l,int r) {
	if(l > r) return 0;
	int id = findseg(root,l,r,0x3f3f3f3f);
//	printf("[%d,%d]-> %d\n",l,r,id);
	if(id > n) return 0;
	return solve(l,ll[id]-1) + solve(rr[id]+1,r) + rr[id]-ll[id]+1;
}
int as[MAXN];
int main() {
	m = read();n = read();
	for(int i = 1;i <= n;i ++) {
		ll[i] = read();rr[i] = read(); b[i] = i;
		p[i].L = p[i].R = p[i].x = ll[i];
		p[i].D = p[i].U = p[i].y = rr[i];
		p[i].mi = 0x3f3f3f3f;p[i].ls = p[i].rs = 0;
		p[i].ii = 0x3f3f3f3f;
	}
	sort(b + 1,b + 1 + n,cmp);
	root = build(1,n,1);
	int id = 0;
	for(int i = m;i > 0;i --) {
		while(id < n && rr[b[id+1]]-ll[b[id+1]]+1 >= i) {
			int y = b[++ id];
			addplane(root,ll[y],rr[y],y,1);
		}
		as[i] = solve(1,m);
	}
	for(int i = 1;i <= m;i ++) {
		printf("%d\n",as[i]);
	}
	return 0;
}
