#include <bits/stdc++.h>
using namespace std;
struct tasks{
  int l,r,idx;
}; vector<tasks> a;
int n,m;
vector<int> worker;
bool init_comp(tasks a,tasks b){
    return a.l<b.l;
}
struct comp{
  bool operator()(tasks a,tasks b){
      return a.l>b.l;
  }
};
priority_queue<tasks, vector<tasks>, comp> from,to;
/*
 * from : 매칭할 때 앞에 올만한 작업
 * to : 매칭할 때 뒤에 오는 작업
 * 각각 끝나는 시점 기준으로 정렬
 */
int main(){
    cin>>n>>m;
    int match_cnt=0;
    a.resize(n);
    worker.resize(n);
    int i,j,l;
    for(i=0;i<n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].idx=i;
    }
    sort(a.begin(),a.end(),init_comp); // 구간 시작 기준으로 정렬
    for(i=0;i<n;i++){
        if(!from.empty() && from.top().r<a[i].l){ // 만약 앞에 오는 작업이랑 매칭 가능하다면?
            worker[from.top().idx]=worker[a[i].idx]=++match_cnt; // 두 작업을 같은 worker에 배정
            from.pop(); // 더 이상 "올만한" 작업이 아님. 이 작업은 무조건 매칭된다고 하자.
            to.push(a[i]); // 뒤에 매칭된 작업은 저장해 둠.
        }
        else if(!to.empty() && to.top().r<a[i].r){ // 만약 "뒤에 오는 작업" 이랑 바꿔치기해서 들어갈 수 있으면?
            // 시작점은 무조건 더 뒤에 있고, if문에 의해 끝점도 더 뒤에 있음.
            // 그러면 앞에 있는 작업을 빼서 "앞에 올만한 작업"에 두는 게 더 그리디함.
            worker[a[i].idx]=worker[to.top().idx];
            worker[to.top().idx]=0;
            from.push(to.top());
            to.pop();
            to.push(a[i]);
        }
        else from.push(a[i]);
    }
    for(i=0;i<n;i++) if(worker[i]==0) worker[i]=++match_cnt;
    for(i=0;i<n;i++){
        if(worker[i]<=m) cout<<worker[i]<<" ";
        else cout<<"0 ";
    }
    cout<<endl;
    // 이거 풀리면 시발 내가 신임
    // by gs22059
}