#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T &x){
	x = 0;
	static char c;
	static bool f;
	c = getchar(), f = 0;
	while(c < '0' || c > '9'){ if(c == '-')f = 1; c = getchar(); }
	while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	x = f ? -x : x;
}
template <typename T,typename ...Types>
inline void read(T &x,Types &...y){
	read(x);
	read(y...);
}

const int N = 5e5 + 10;
using pii = pair<int,int>;
priority_queue<pii,vector<pii>,greater<pii> > a,b;
int n,ans[N],m;
int match[N],mp[N];
struct P{
	int l,r,id;
	bool friend operator <(const P &a,const P &b){
		return a.l == b.l ? a.r < b.r : a.l < b.l;
	}
}s[N];



int main(){
	read(n),read(m);
	for(int i = 1;i<=n;++i)read(s[i].l,s[i].r),s[i].id = i;
	sort(s+1,s+n+1);
	for(int i = 1;i<=n;++i){
		int l = s[i].l, r = s[i].r, id = s[i].id;
		mp[i] = id;
		if(a.size() && a.top().first < l){
			match[mp[a.top().second]] = id;
			match[id] = mp[a.top().second];
			a.pop(),b.push({r,i});
		}
		else if(b.size() && b.top().first < r){
			int to = match[mp[b.top().second]];
			match[to] = id, match[id] = to;
			match[mp[b.top().second]] = 0;
			a.push(b.top()),b.pop(),b.push({r,i});
		}
		else a.push({r,i});
	}
	int tot = 0;
	for(int i = 1;i<=n;++i){
		if(match[i]){
			ans[i] = ans[match[i]] = ++tot;
			match[match[i]] = 0;
		}
	}
	for(int i = 1;i<=n;++i){	
		(ans[i] == 0) && (ans[i] = ++tot);
		printf("%d ",ans[i] > m ? 0 : ans[i]);
	}
	return 0;
}