#include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define fileerr(x) freopen(x, "w", stderr);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 333333;
int n, m, ans[N];
struct Node{int l, r, id;}a[N];
priority_queue<pii, vector<pii>, greater<pii>> p, q;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
	stable_sort(a+1, a+1+n, [&](Node a, Node b){return a.l < b.l;});
	for (int i=1; i<=n; i++)
	{
		if (!p.empty() && (p.top().first < a[i].l))
		{
			ans[p.top().second] = ans[a[i].id] = m;
			p.pop(); q.push({a[i].r, a[i].id}); --m;
		}
		else if (!q.empty() && (q.top().first < a[i].r))
		{

			ans[a[i].id] = ans[q.top().second];
			ans[q.top().second] = 0;
			p.push(q.top()); q.pop(); q.push({a[i].r, a[i].id});
		}
		else p.push({a[i].r, a[i].id});
		if (!m) break;
	}
	for (int i=1; i<=n; i++)
		if (!ans[i] && m) ans[i] = m--;
	for (int i=1; i<=n; i++) printf("%d ", ans[i]); puts("");
	return 0;
}