#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3e5+5;
struct node
{
	int x,y,id;
	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,pos[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;
	n=read();m=read();
	for(i=1;i<=n;i++)
	{
		a[i].x=read();a[i].y=read();a[i].id=i;
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		if(q.size()&&q.top().val<a[i].x)
		{
			p.push((edge){a[i].id,a[i].y});
			pos[q.top().id]=pos[a[i].id]=m--;q.pop();
			if(!m)
			break;
		}
		else
		{
			if(p.size()&&p.top().val<a[i].y)
			{
				q.push(p.top());
				pos[a[i].id]=pos[p.top().id];
				pos[p.top().id]=0;
				p.pop();p.push((edge){a[i].id,a[i].y});
			}
			else
			q.push((edge){a[i].id,a[i].y});
		}
	}
	for(i=1;i<=n&&m;i++)
	if(!pos[i])
	pos[i]=m--;
	for(i=1;i<=n;i++)
	printf("%d ",pos[i]);
	return 0;
}