#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int n,m;
struct Seg{
	int l,r,id;
	bool operator <(const Seg &y)const{
		return l<y.l;
	}
}a[300005];
struct node{
	int p,id;
	bool operator <(const node &y)const{
		if (p==y.p)return id<y.id;
		return p<y.p;
	}
};
node make_node(int p,int id){
	node ans;
	ans.p=p,ans.id=id;
	return ans;
}
set<node> c,d;
int t[300005];
int ans[300005];
int main(){
	cin>>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+1+n);
	for (int i=1;i<=n;i++){
		set<node>::iterator it=c.begin();
		if (it!=c.end()&&((*it).p<a[i].l)){
			t[a[i].id]=(*it).id;
			c.erase(it);
			d.insert(make_node(a[i].r,a[i].id));
		}
		else{
			it=d.begin();
			if (it!=d.end()&&((*it).p<a[i].r)){
				t[a[i].id]=t[(*it).id];
				t[(*it).id]=0;
				d.erase(it);
				c.insert((*it));
				d.insert(make_node(a[i].r,a[i].id));
			}
			else c.insert(make_node(a[i].r,a[i].id));
		}
	}
	for (int i=1;i<=n;i++)
		if (m>0&&t[i]>0)ans[t[i]]=ans[i]=m,m--;
	for (int i=1;i<=n;i++)
		if (m>0&&ans[i]==0)ans[i]=m,m--;
	for (int i=1;i<=n;i++)printf("%d ",ans[i]);
	cout<<endl; 
	return 0;
}