#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));
if (tot == m) break;
}
_for (i, 1, n) {
if (tot == m) break;
if (!ans[i]) ans[i] = ++tot;
}
return;
}
void Out () {
_for (i, 1, n) printf ("%d ", ans[i]);
puts ("");
std::cerr << tot << std::endl;
return;
}
}
int main () {
SOLVE::In ();
SOLVE::Solve ();
SOLVE::Out ();
return 0;
} /*
*/