#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3e5+5;
struct node
{
	int x,y;
	friend bool operator < (node p,node q)
	{
		return p.x<q.x;
	}
}a[N];
struct edge
{
	int id,val;
	friend bool operator < (edge x,edge y)
	{
		return x.val>y.val;
	}
};
int n,m,ak[N],bk[N],pos[N],outp[N];
priority_queue<edge> p,q;
int read()
{
	int res,f=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9')
	if(ch=='-')
	f=-1;
	res=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
	res=(res<<1)+(res<<3)+(ch^48);
	return res*f;
}
int main()
{
	int i,x,ans=0,cnt=0;
	n=read();m=read();
	for(i=1;i<=n;i++)
	{
		a[i].x=read();a[i].y=read();
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		if(q.size()&&q.top().val<=a[i].x)
		{
			p.push((edge){i,a[i].y});
			ans++;ak[ans]=q.top().id;bk[ans]=i;
			pos[q.top().id]=pos[i]=ans;
			q.pop();
		}
		else
		{
			if(p.size()&&p.top().val<=a[i].y)
			{
				q.push(p.top());
				bk[pos[i]=pos[p.top().id]]=i;
				pos[p.top().id]=0;
				p.pop();p.push((edge){i,a[i].y});
			}
			else
			q.push((edge){i,a[i].y});
		}
	}
	if(m+ans>=n)
	{
		x=m+ans-n;
		for(i=1;i<=x;i++)
		{
			outp[ak[i]]=++cnt;
			outp[bk[i]]=++cnt;
		}
		for(i=x+1;i<=ans;i++)
		outp[ak[i]]=outp[bk[i]]=++cnt;
		for(i=1;i<=n;i++)
		if(!outp[i])
		outp[i]=++cnt;
	}
	else
	{
		for(i=1;i<=ans;i++)
		outp[ak[i]]=outp[bk[i]]=++cnt;
		for(i=1;i<=n&&cnt<=m-1;i++)
		if(!outp[i])
		outp[i]=++cnt;
	}
	for(i=1;i<=n;i++)
	printf("%d ",outp[i]);
	return 0;
}