#include<bits/stdc++.h> // header
using namespace std; // std function
#define int long long
#define elif else if // redirect
#define fall(x) (x).begin(), (x).end() // macro
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) // macro
// struct
struct cliques{int loc,lr,i;};
struct tasks{int l,r,idx;};
struct pq_comp{bool operator()(pair<int,int> a, pair<int,int> b){return a.first>b.first;}};
// comparators
bool fmq_comp(const cliques a, const cliques b){
    if(a.loc!=b.loc)return a.loc<b.loc;
    return a.lr<b.lr;
}
bool col_comp(const tasks a, const tasks b){return a.l<b.l;}
bool col_reset_comp(const tasks a, const tasks b){return a.idx<b.idx;}
bool align_right_normal(const tasks a, const tasks b){return a.r<b.r;}
bool align_left_normal(const tasks a, const tasks b){return a.l<b.l;}
bool align_right_inverse(const tasks a, const tasks b){return a.r>b.r;}
bool align_left_inverse(const tasks a, const tasks b){return a.l>b.l;}
// variable declarations
vector<int> maximum_clique, non_maximum_clique, max_left, max_right;
vector<tasks> task_list;
vector<cliques> fmq_list; // 최대 클리크 찾기용 누적합
priority_queue<pair<int, int>, vector<pair<int, int>>, pq_comp> color_last; // 색상별 구간 중 가장 오른쪽 위치
vector<pair<int, int>> bipartite_matches; // 이분 매칭 리스트
vector<tasks> list_max, list_max_left, list_max_right;
set<int> colors[400000]; // 색상별 정점 리스트
int m,n,l[400000],r[400000]; // 입력
int bipartite_match_idx[400000]; // 이분 매칭한 게 있는 경우 해당 정점의 인덱스, 아니면 -1
int task_color[400000]; // 정점 색상
int color_count[400000]; // 색상별 정점 수
int workers[400000]; // 작업 매칭
// function declarations
void init(){ // 초기화 및 입력
    memset(bipartite_match_idx,-1,sizeof(bipartite_match_idx));
    memset(workers,-1,sizeof(workers));
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>l[i]>>r[i];
        task_list.push_back({l[i],r[i],i});
    }
}

void find_maximum_clique(){ // 최대 클리크 찾아서 원소 저장, 최대 클리크 아닌 것은 따로 저장
    int i,max_location=0, max_number=0,a=0;
    for(i=0;i<(int)task_list.size();i++){
        fmq_list.push_back({task_list[i].l,1,i});
        fmq_list.push_back({task_list[i].r+1,-1,i});
    }
    sort(fall(fmq_list),fmq_comp);
    for(i=0;i<(int)fmq_list.size();i++){
        a+=fmq_list[i].lr;
        if(a>max_number){
            max_number=a;
            max_location=fmq_list[i].loc;
        }
    }
    for(i=0;i<(int)task_list.size();i++){
        if(task_list[i].l<=max_location && task_list[i].r>=max_location){
            maximum_clique.push_back(task_list[i].idx);
        }
        else non_maximum_clique.push_back(task_list[i].idx);
    }
}

void coloring(){ // 탐욕적으로 구간 색상 지정, 증명 가능
    int i;
    sort(fall(task_list),col_comp);
    for(i=0;i<(int)maximum_clique.size();i++){
        task_color[task_list[i].idx]=i;
        color_last.push({task_list[i].r,i});
        color_count[i]=1;
        colors[i].insert(task_list[i].idx);
    }
    for(i=(int)maximum_clique.size();i<(int)task_list.size();i++){
        pair<int, int> tmp=color_last.top();
        color_last.pop();
        tmp.first=task_list[i].r;
        task_color[task_list[i].idx]=tmp.second;
        color_count[tmp.second]++;
        colors[tmp.second].insert(task_list[i].idx);
        color_last.push(tmp);
    }
    sort(fall(task_list),col_reset_comp);
}

void left_right_division(){ // 최대 클리크에 속하지 않은 것을 왼쪽과 오른쪽으로 분리해 저장
    int max_clique_start=0,max_clique_end=(int)1e9,i,j;
    for(i=0;i<(int)maximum_clique.size();i++){
        list_max.push_back(task_list[maximum_clique[i]]);
        if(task_list[maximum_clique[i]].l>max_clique_start){
            max_clique_start=task_list[maximum_clique[i]].l;
        }
        if(task_list[maximum_clique[i]].r<max_clique_end){
            max_clique_end=task_list[maximum_clique[i]].r;
        }
    }
    for(i=0;i<(int)non_maximum_clique.size();i++){
        if(task_list[non_maximum_clique[i]].r<max_clique_start){
            max_left.push_back(non_maximum_clique[i]);
            list_max_left.push_back(task_list[non_maximum_clique[i]]);
        }
        if(task_list[non_maximum_clique[i]].l>max_clique_end){
            max_right.push_back(non_maximum_clique[i]);
            list_max_right.push_back(task_list[non_maximum_clique[i]]);
        }
    }
}
void bipartite_matching(){ // 최대 클리크에 속한 것과 그렇지 않은 것 사이를 left_right_division 에서 저장한 것을 이용해 이분 매칭
    int i,j;
    sort(list_max_right.begin(),list_max_right.end(),align_left_normal);
    sort(list_max.begin(),list_max.end(),align_right_normal);
    bool chk[300000]={0};
        for(i=0,j=0; j<(int)list_max.size();j++){
            while(i<(int)list_max_right.size() && list_max_right[i].l<=list_max[j].r) i++;
            if(i>=(int)list_max_right.size()) break;
            bipartite_matches.emplace_back(list_max[j].idx,list_max_right[i].idx);
            chk[list_max[j].idx]=true;
            bipartite_match_idx[list_max_right[i].idx]=list_max[j].idx;
            bipartite_match_idx[list_max[j].idx]=list_max_right[i].idx;
        }
        sort(list_max.begin(),list_max.end(),align_left_normal);
        sort(list_max_left.begin(),list_max_left.end(),align_right_normal);
        for(i=0,j=0; j<(int)list_max.size();j++){
            while(i<(int)list_max_left.size() &&
                  (list_max_left[i].r>=list_max[j].l || chk[list_max[j].idx]==1)) i++;
            if(i>=(int)list_max_left.size()) break;
        bipartite_matches.emplace_back(list_max[j].idx,list_max_left[i].idx);
        bipartite_match_idx[list_max_left[i].idx]=list_max[j].idx;
        bipartite_match_idx[list_max[j].idx]=list_max_left[i].idx;
    }
}

void maximize_couples(){ // 크기 1인 독립집합 (즉 최대 클리크에 속한 것들) 중 이분 매칭에 따라 매칭 가능한 것 최대한 매칭
    vector<int> single;
    int i;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(color_count[i]==1) single.push_back(i);
    }
    while(!single.empty()){
        int idx=*colors[single.back()].begin();
        single.pop_back();
        if(bipartite_match_idx[idx]!=-1){
            int id2=bipartite_match_idx[idx], id2_col=task_color[id2];
            bipartite_match_idx[idx]=bipartite_match_idx[id2]=-1;
            color_count[id2_col]--; color_count[task_color[idx]]++;
            colors[id2_col].erase(id2);
            colors[task_color[idx]].insert(id2);
            task_color[id2]=task_color[idx];
            if(color_count[id2_col]==1){
                single.push_back(id2_col);
            }
        }
    }
}

void left_right_bipartite(){ // 만약 모든 색에 대해 해당 색을 가진 구간이 "모두" 두 개 이상이거나 이하이면 굳이 이분 매칭을 하지 않아도 됨
    int i; bool x=0,y=0;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(color_count[i]<2) x=1;
        if(color_count[i]>2) y=1;
    }
    if(x&&y){
        left_right_division();
        bipartite_matching();
        maximize_couples();
    }
}

void workers_matching(){ // 완성한 매칭에 따라 "학생" 부여
    int cnt=0,i,j;
    vector<int> single, even;
    vector<vector<int>> odd;
    for(i=0;i<(int)maximum_clique.size();i++){
        if(colors[i].size()%2==0){
            for(auto it : colors[i]) even.push_back(it);
            for(j=0;j<(int)even.size()-1;j+=2){
                workers[even[j]]=cnt;
                workers[even[j+1]]=cnt++;
            }
            even.clear();
        }
        elif(colors[i].size()%2==1 && colors[i].size()>1){
            odd.push_back({});
            for(int it : colors[i]) odd.back().push_back(it);
        }
    }
    for(i=0;i<(int)odd.size()-1;i+=2){
        if((int)odd.size()==1) break;
        int s1=odd[i].size()-1, s2=odd[i+1].size()-1;
        if(task_list[odd[i][s1-1]].l>task_list[odd[i][s1]].r) swap(odd[i][s1-1],odd[i][s1]);
        if(task_list[odd[i+1][s2-1]].l>task_list[odd[i+1][s2]].r) swap(odd[i+1][s2-1],odd[i+1][s2]);
        if(task_list[odd[i][s1-1]].r<task_list[odd[i+1][s2]].l){
            workers[odd[i][s1-1]]=cnt;
            workers[odd[i+1][s2]]=cnt++;
            odd[i][s1-1]=odd[i][s1];
        }
        else{
            workers[odd[i][s1]]=cnt;
            workers[odd[i+1][s2-1]]=cnt++;
            odd[i+1][s2-1]=odd[i+1][s2];
        }
        for(j=0;j<s1-1;j+=2){
            workers[odd[i][j]]=cnt;
            workers[odd[i][j+1]]=cnt++;
        }
        for(j=0;j<s2-1;j+=2){
            workers[odd[i+1][j]]=cnt;
            workers[odd[i+1][j+1]]=cnt++;
        }
    }
    if((int)odd.size()%2==1){
        for(i=0;i<(int)odd.back().size()-1;i+=2){
            workers[odd.back()[i]]=cnt;
            workers[odd.back()[i+1]]=cnt++;
        }
        workers[odd.back().back()]=cnt++;
    }
    for(i=0;i<(int)maximum_clique.size();i++){
        if(colors[i].size()==1){
            workers[*colors[i].begin()]=cnt++;
        }
    }
}

void output(){ // 이거 ㄹㅇ 어려움 진짜 어떻게 이런 함수를 짤 생각을 했냐
    int i;
    for(i=0;i<n;i++) {
        if(workers[i]<m) cout<<workers[i]+1<<" ";
        else cout<<0<<" ";
    }
}

signed main(){
    fast;
    init(); // O(n)
    find_maximum_clique(); // O(n log n)
    coloring(); // O(n log n)
    left_right_bipartite(); // O(n log n)
    workers_matching(); // O(n) probably
    output(); // O(n)
    return 0;
}