#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e6 + 10;
const int INF = 2e9;
int n, m, tot;
int f[N], lsh[N];
pii a[N];
struct Node {int x, y;};
bool operator < (Node x, Node y) {
  if(a[x.y].SE != a[y.y].SE)return a[x.y].SE < a[y.y].SE;
  return x.x < y.x;
}
set<Node> st[N];
void disc() {
  for(int i = 1; i <= n; i++)lsh[++tot] = a[i].FR, lsh[++tot] = a[i].SE;
  sort(lsh + 1, lsh + 1 + tot);
  tot = unique(lsh + 1, lsh + 1 + tot) - (lsh + 1);
  for(int i = 1; i <= n; i++) {
    a[i].FR = lower_bound(lsh + 1, lsh + 1 + tot, a[i].FR) - lsh;
    a[i].SE = lower_bound(lsh + 1, lsh + 1 + tot, a[i].SE) - lsh;
  }
  return ;
}
Node mn[N << 2];
void update(int k, int l, int r, int x) {
  if(l == r) {
    if(!st[l].size())mn[k] = {0, 0};
    else mn[k] = *st[l].begin();
    return ;
  }
  int mid = l + r >> 1;
  if(x <= mid)update(k << 1, l, mid, x);
  else update(k << 1 | 1, mid + 1, r, x);
  mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
  return ;
}
Node query(int k, int l, int r, int qx, int qy) {
  if(l >= qx && r <= qy)return mn[k];
  int mid = l + r >> 1; Node res = {0, 0};
  if(qx <= mid)res = min(res, query(k << 1, l, mid, qx, qy));
  if(qy > mid)res = min(res, query(k << 1 | 1, mid + 1, r, qx, qy));
  return res;
}
void ins(int x) { 
  st[a[x].SE].insert({x, f[x]});
  update(1, 1, tot, a[x].SE);
  return ;
}
void del(int x) {
  // if(!st[a[x].SE].count({x, f[x]})) {
  //   cout << "fail:" << x << ' ' << f[x] << ' ' << st[a[x].SE].size() << endl;
  //   for(auto t : st[a[x].SE])printf("%d %d\n", t.x, t.y);
  // }
  st[a[x].SE].erase({x, f[x]});
  update(1, 1, tot, a[x].SE);
  return ;
}
int col[N];
int main() {
  n = read(); m = read();
  for(int i = 1; i <= n; i++)a[i].FR = read(), a[i].SE = read();
  disc();
  vector<int> p(n);
  iota(p.begin(), p.end(), 1);
  sort(p.begin(), p.end(), [&](int x, int y) {return a[x] < a[y];});
  a[0].SE = INF;
  // for(int i = 1; i <= n; i++)printf("%d %d\n", a[i].FR, a[i].SE);
  // vector<int> wait, mat;
  multiset<pii> wait;
  int ans = 0;
  for(int j = 0; j < n; j++) {
    int mx = 0, pos = -1, i = p[j];
    // for(int j = 0; j < wait.size(); j++) {
    //   if(a[wait[j]].SE < a[i].FR) {
    //     if(a[wait[j]].SE > mx) {
    //       mx = a[wait[j]].SE;
    //       pos = j;
    //     }
    //   }
    // }
    auto it = wait.lower_bound({a[i].FR, 0});
    if(it != wait.begin()) {
      it--; int pos = it->SE;
      f[pos] = i; f[i] = pos;
      wait.erase(it);
      ins(pos); ins(i);
      // cout << "size:" << st[a[pos].SE].size() << ' ' << st[a[i].SE].size() << endl;
      // cout << i << ' ' << pos << endl;
    }
    // if(~pos) {
    //   f[wait[pos]] = i; f[i] = wait[pos];
    //   mat.pb(i); mat.pb(wait[pos]);
    //   wait.erase(wait.begin() + pos);
    // }
    else {
      Node v = (a[i].FR > 1 ? query(1, 1, tot, 1, a[i].FR - 1) : (Node){0, 0});
      if(v.x && a[v.y].SE < a[i].SE) {
        del(v.x); del(f[v.x]);
        // cout << "v:" << i << ' ' << v.x << ' ' << v.y << endl;
        wait.insert({a[v.y].SE, v.y});
        f[i] = v.x; f[v.x] = i;
        ins(i); ins(v.x); f[v.y] = 0;
      }
      else wait.insert({a[i].SE, i});
      // else wait.insert({a[i].SE, i});
      // int mn = a[i].SE; pos = -1;
      // for(int j = 0; j < mat.size(); j++) {
      //   if(a[mat[j]].SE < a[i].FR) {
      //     if(a[f[mat[j]]].SE < mn) {
      //       mn = a[f[mat[j]]].SE;
      //       pos = j;
      //     }
      //   }
      // }
      // // cout << "chai:" << i << ' ' <<mn << ' ' << pos << endl;
      // if(~pos) {
      //   int v = f[mat[pos]];
      //   f[mat[pos]] = i; f[i] = mat[pos]; mat.pb(i);
      //   mat.erase(find(mat.begin(), mat.end(), v));
      //   wait.pb(v);
      // }
      // else wait.pb(i);
    }
    // printf("greedyt:%d\n", i);
    // for(int x : wait)printf("%d ", x); putchar('\n');
    // for(int x : ma)printf("%d ", x); putchar('\n');
    // cout << "qwq:" << j << ' ' << i << endl;
    // for(int i = 1; i <= n; i++)cout << f[i] << endl;
  }
  int cnt = 0;
  for(int i = 1; i <= n && cnt < m; i++)
    if(i < f[i])col[i] = col[f[i]] = ++cnt, ans += 2;
  for(int i = 1; i <= n && cnt < m; i++)
    if(!col[i])col[i] = ++cnt, ans++;
  // printf("%d\n", ans);
  for(int i = 1; i <= n; i++)printf("%d ", col[i]); putchar('\n');
  return 0;
}