#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;
pii s[N];
int n,ans[N],m;
int match[N];
int main(){
	read(n),read(m);
	for(int i = 1;i<=n;++i)read(s[i].first,s[i].second);
	sort(s+1,s+n+1);
	for(int i = 1;i<=n;++i){
		pii p = s[i];
		int l = p.first, r = p.second;
		if(a.size() && a.top().first < l){
			match[a.top().second] = i;
			match[i] = a.top().second;
			a.pop(),b.push({r,i});
		}
		else if(b.size() && b.top().first < r){
			int to = match[b.top().second];
			match[to] = i, match[i] = to;
			match[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;
}