#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
namespace IO {
	int rnt () {
		int x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
} // namespace IO
const int N = 5e5 + 10, P = 998244353;
namespace SOLVE {
	using namespace IO;
	int n, m, ans[N];
	class R {
	public:
		int l, r, id;
		R () = default;
		R (int _l, int _r, int _id) : l (_l), r (_r), id (_id) {}
	} rg[N];
	void In () {
		n = rnt (), m = rnt ();
		_for (i, 1, n) {
			int l = rnt (), r = rnt ();
			rg[i] = R (l, r, i);
		}
		return;
	}
	void Solve () {
		std::sort (rg + 1, rg + n + 1, [&] (R a, R b) {
			return a.l == b.l ? a.r < b.r : a.l < b.l; });
		std::priority_queue <pii, std::vector <pii>, std::greater <pii> > q[2];
		int tot = 0;
		_for (i, 1, n) {
			if (!q[0].empty () && q[0].top ().first < rg[i].l) {
				ans[q[0].top ().second] = ans[rg[i].id] = ++tot;
				q[1].push (pii (rg[i].r, rg[i].id)), q[0].pop ();
			}
			else if (!q[1].empty ()) {
				ans[rg[i].id] = ans[q[1].top ().second];
				ans[q[1].top ().second] = 0;
				q[0].push (q[1].top ()), q[1].pop ();
				q[1].push (pii (rg[i].r, rg[i].id));
			}
			else q[0].push (pii (rg[i].r, rg[i].id));
		}
		while (!q[0].empty () && tot < m) ans[q[0].top ().second] = ++tot, q[0].pop ();
		return;
	}
	void Out () {
		_for (i, 1, n) printf ("%d ", ans[i]);
		puts ("");
		return;
	}
}
int main () {
	SOLVE::In ();
	SOLVE::Solve ();
	SOLVE::Out ();
	return 0;
} /*

*/