#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
struct node{
	int l,r;
}a[N];
int p[N];
bool cmp(const int &A,const int &B){
	return a[A].l<a[B].l;
}
int n,m,ans[N];
struct node2{
	int id;
	bool operator < (const node2 &rhs)const{
		return a[id].r>a[rhs.id].r;
	}
};
struct node3{
	int id1,id2;
	bool operator < (const node3 &rhs)const{
		return a[id2].r>a[rhs.id2].r;
	}
};
priority_queue<node2> q1;
priority_queue<node3> q2;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&a[i].l,&a[i].r),p[i]=i;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;++i){
		if(!q1.empty()&&a[q1.top().id].r<a[p[i]].l){
			int x=q1.top().id;
			q1.pop();
			q2.push((node3){x,p[i]});
		}
		else if(!q2.empty()&&a[q2.top().id2].r<a[p[i]].r){
			int x=q2.top().id1,y=q2.top().id2;
			q2.pop();
			q2.push((node3){x,p[i]});
			q1.push((node2){y});
		}
		else q1.push((node2){p[i]});
	}
	int id=0;
	while(!q2.empty()&&id<m){
		int x=q2.top().id1,y=q2.top().id2;
		q2.pop();
		ans[x]=ans[y]=++id;
	}
	while(!q1.empty()&&id<m){
		int x=q1.top().id;
		q1.pop();
		ans[x]=++id;
	}
	for(int i=1;i<=n;++i)
		printf("%d ",ans[i]);
	return 0;
}