#include <bits/stdc++.h>
using namespace std;
#define N 300005
int n,m,ps[N],ans[N];
struct Range
{
	int l,r,id;
	bool operator < (Range t) const
	{return l==t.l?r<t.r:l<t.l;}
}a[N];
struct Node
{
	int x,id;
	bool operator < (Node t) const
	{return x==t.x?id<t.id:x<t.x;}
};set<Node> z1,z2;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)	
		scanf("%d %d",&a[i].l,&a[i].r),a[i].id=i;
	sort(a+1,a+n+1);
	for(int i=1,l,r,id;i<=n;++i)
	{
		l=a[i].l;r=a[i].r;id=a[i].id;
		set<Node>::iterator it;
		if(!z1.empty())
		{
			it=z1.lower_bound((Node) {l,0});
			if(it!=z1.begin())
			{
				--it;ps[id]=it->id;z1.erase(it);
				z2.insert((Node) {r,id});continue;
			}
		}
		if(!z2.empty())
		{
			it=z2.begin();
			if(r>it->x)
			{
				ps[id]=ps[it->id];ps[it->id]=0;
				z1.insert(*it);z2.erase(it);
				z2.insert((Node) {r,id});continue;
			}
		}z1.insert((Node) {r,id});
	}
	for(int i=1;i<=n;++i) if(ps[i])
		ans[i]=ans[ps[i]]=++ans[0];
	for(int i=1;i<=n;++i) if(!ans[i]) ans[i]=++ans[0];
	for(int i=1;i<=n;++i)
		printf("%d ",ans[i]<=m?ans[i]:0);return 0;
}