#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<tuple<int, int,int>> s(N);
  for (int i = 0; i < N; i++) {
    auto &[l, r, id] = s[i];
    cin >> l >> r;
    id = i;
  }
  ranges::sort(s);

  multimap<int, int, greater<>> st;

  vector<int> ans(N, -1);
  // vector<int> match(N, -1);
  int mat = 0;

  for (auto [l, r, i] : s) {
    auto it = st.upper_bound(l);
    if (it != st.end()) {
      // match[i] = it->second;
      // match[it->second] = i;
      ans[i] = ans[it->second] = mat++;
      if (mat == M)
        break;
      st.erase(it);
    } else {
      st.insert({r, i});
    }
  }

  for (int i = 0; i < N && mat < M; i++)
    if (ans[i] == -1)
      ans[i] = mat++;

  for (int i = 0; i < N; i++)
    cout << ans[i] + 1 << (i+1==N ? '\n' : ' ');
}