// Author: wlzhouzhuan
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fir first
#define sec second
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, t) memset(s, t, sizeof(s))
#define mcpy(s, t) memcpy(s, t, sizeof(t))
#define poly vector<int>
#define SZ(x) (int(x.size()))
template<typename T1, typename T2> void ckmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> void ckmax(T1 &a, T2 b) { if (a < b) a = b; }
int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 400005;

struct node {
  int l, r, id;
  friend bool operator < (const node &x, const node &y) {
    return x.l < y.l;
  }
} a[N];
int lnk[N], n, m;
int ans[N];

multiset<pii> A, B;

int main() {
  n = read(), m = read();
  rep(i, 1, n) a[i].l = read(), a[i].r = read(), a[i].id = i;
  sort(a + 1, a + n + 1);
  rep(i, 1, n) {
    if (!A.empty() && A.begin()->fir < a[i].l) {
      int t = A.begin()->fir, who = A.begin()->sec;
      A.erase(A.begin());
      B.insert({a[i].r, i});
      lnk[who] = i, lnk[i] = who;
    } else {
      if (B.empty() || B.begin()->fir >= a[i].r) {
        A.insert({a[i].r, i});
      } else {
        int who = B.begin()->sec, who2 = lnk[who];
        lnk[who2] = i, lnk[i] = who2, lnk[who] = 0;
        A.insert(*B.begin());
        B.erase(B.begin());
        B.insert({a[i].r, i});
      }
    }
  }
  while (SZ(B) > m) B.erase(B.begin());
  int tot = 0;
  for (auto &it: B) {
    int aa = it.sec, bb = lnk[aa];
    ans[a[aa].id] = ans[a[bb].id] = ++tot;
  }
  rep(i, 1, n) {
    if (!ans[i] && tot < m) ans[i] = ++tot;
    print(ans[i], " \n"[i == n]);
  }
  return 0;
}