#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+3;
int n,m,ans[N];
bool v[N];
struct Nod{int l,r,id;}a[N],b[N];
bool CL(Nod a,Nod b){return a.l<b.l;}
bool CR(Nod a,Nod b){return a.r<b.r;}
bool Chk(int x)
{
	for(int i=1;i<=x;i++)if(a[i].r>=b[n-x+i].l)return 0;
	return 1;
}
int main()
{
	cin>>n>>m;int l=0,r=n/2;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r,a[i].id=i,b[i]=a[i];
	sort(a+1,a+n+1,CR);sort(b+1,b+n+1,CL);
	while(l<r)
	{
		int mi=(l+r)/2+1;
		Chk(mi)?l=mi:r=mi-1; 
	}
	for(int i=1;i<=min(m,l);i++)
	    ans[a[i].id]=ans[b[n-l+i].id]=i,v[a[i].id]=v[b[n-l+i].id]=1;
	//for(int i=1;i<=n&&l<m;i++)if(!v[i])ans[i]=++l;
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}