#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+15;
inline ll read(){
	ll x=0;char f=1,c=getchar();
	while(c<48||c>57){if(c=='-')f=0;c=getchar();}
	while(c>=48&&c<=57){x=(x<<1)+(x<<3)+ll(c)-48;c=getchar();}
	return f==1?x:-x;
}
int n,m,p[N],l[N],r[N],vl[N],vr[N],ans[N];
inline bool cmpl(int x,int y){return l[x]>l[y];}
inline bool cmpr(int x,int y){return r[x]<r[y];}
inline bool check(int x){
	for(int i=1,j=x;i<=x;++i,--j){
		if(r[vr[i]]>=l[vl[j]])return false;
	}
	return true;
}
inline void mk(int x){
	fill(ans+1,ans+n+1,0);
	for(int i=1,j=x;i<=x;++i,--j){
		ans[vr[i]]=i,ans[vl[j]]=i;
	}
	int cnt=x+1;
	for(int i=1;i<=n&&cnt<=m;++i){
		if(!ans[i])ans[i]=cnt++;
	}
}
int solve(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		l[i]=read(),r[i]=read();
	}
	for(int i=1;i<=n;++i)p[i]=i;
	sort(p+1,p+n+1,cmpr);
	for(int i=1;i<=n;++i)vr[i]=p[i];
	sort(p+1,p+n+1,cmpl);
	for(int i=1;i<=n;++i)vl[i]=p[i];
	int l=0,r=m,mid=0,mx=0;
	while(l<=r){
		mid=((l+r)>>1);
		if(check(mid))mx=mid,l=mid+1,mk(mid);
		else r=mid-1;
	}
	for(int i=1;i<=n;++i)printf("%d ",ans[i]);
	printf("\n");
	return 0;
}
/*
5
9 13
3 7
9 12
7 10
3 7
2

10
37 41
78 84
30 37
94 98
52 58
3 9
76 83
58 62
50 56
17 25
5

7
9 10
7 9
3 4
9 10
2 6
8 9
5 8
3
*/
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=1;
	while(T--){
		solve();
	}
	fclose(stdin),fclose(stdout);
	return 0;
}