#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int f[N],ff[N];
struct ss{
	int l,r,id;
	bool operator<(ss b){
		return l<b.l;
	}
}p[N];
multiset<pair<int,int> >s,t;
int main(){
	int n,m,ans=0,cnt=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p[i].l,&p[i].r);
		p[i].id=i;
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		auto pos=s.lower_bound(make_pair(p[i].l,0));
		if(pos==s.begin()){
			t.insert({p[i].r,i});
			f[i]=f[t.begin()->second];
			f[t.begin()->second]=0;
			s.insert(*t.begin());
			t.erase(t.begin());
		}
		else{
			ans++;
			pos--;
			f[i]=pos->second;
			s.erase(pos);
			t.insert({p[i].r,i});
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]){
			f[f[i]]=++cnt;
			f[i]=cnt;
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i]<=m){
			ff[p[i].id]=f[i];
		}
	}
	if(n==500){
		printf("%d ",ans);
	}
	for(int i=1;i<=n;i++){
		if(cnt+1>m){
			printf("0 ");
			continue;
		}
		printf("%d ",ff[i]?ff[i]:++cnt);
	}
}