#include<bits/stdc++.h>
using namespace std;
int n,m,j=1,p=1,l,r,mid,res,ans[500005],cnt;
struct node{int l,r,id;}a[500005],b[500005];
inline bool cmp1(node a,node b){return a.r<b.r;}
inline bool cmp2(node a,node b){return a.l<b.l;}
inline bool check(int x)
{
	for(int i=1;i<=x;++i) if(a[i].r>=b[n-x+i].l) return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m),l=1,r=n/2;
	for(int i=1;i<=n;++i) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i,b[i]=a[i];
	sort(a+1,a+n+1,cmp1),sort(b+1,b+n+1,cmp2);
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid)) l=mid+1,res=mid;
		else r=mid-1;
	}
	for(int i=1;i<=res;++i)
	{
		ans[a[i].id]=ans[b[n-res+i].id]=++cnt;
	}
	for(int i=1;i<=n;++i)
	{
		if(!ans[i]) ans[i]=++cnt;
		printf("%d ",(ans[i]<=m)?ans[i]:0);
	}
	return 0;
}