#include<bits/stdc++.h>
const int maxn=100000+10,maxm=100000+10;
using namespace std;
int a[maxn<<2],c[maxn];
void init(int h,int s,int t){
	if(s==t) a[h]=0;
	else{
		init(h*2,s,(s+t)/2);
		init(h*2+1,(s+t)/2+1,t);
	}
}
void ts(int h,int s,int t,int L,int R,int ys){
	if(L<=s&&t<=R) a[h]=ys;
	else{
		if(a[h]>=0){
			a[h*2]=a[h*2+1]=a[h];
			a[h]=-1;
		}
		if(L<=(s+t)/2) ts(h*2,s,(s+t)/2,L,R,ys);
		if((s+t)/2+1<=R) ts(h*2+1,(s+t)/2+1,t,L,R,ys);
	}
}
void cal(int h,int s,int t){
	 if(a[h]>=0) c[a[h]]+=t-s+1;
	 else{
	 	cal(h*2,s,(s+t)/2);
	 	cal(h*2+1,(s+t)/2+1,t);
	 }
}


int main(){
	int i,j,k,m,n,x,y;
	cin>>n>>m;
	init(1,1,n);
	for(i=1;i<=m;i++){
		cin>>x>>y;
		ts(1,1,n,x,y,i);
	}
	cal(1,1,n);
	for(i=0;i<=m;i++)
	if(c[i]) cout<<i<<c[i]<<endl;







	return 0;
}