#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
struct seg{
  int l,r,id;
}a[300010];
int n,m,ans[300010];
priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>>x,y;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        a[i].id=i;
    }
    sort(a+1,a+n+1,[](seg &a,seg &b){return a.l<b.l;});
    for(int i=1;i<=n&&m;i++){
        if(!x.empty()&&x.top().fi<a[i].l){
            ans[x.top().se]=ans[a[i].id]=m--;
            x.pop();
            y.push({a[i].r,a[i].id});
        }
        else if(!y.empty()&&y.top().fi<a[i].r){
            ans[a[i].id]=ans[y.top().se],ans[y.top().se]=0;
            x.push(y.top()),y.pop();
            y.push({a[i].r,a[i].id});
        }
        else x.push({a[i].r,a[i].id});
    }
    for(int i=1;i<=n;i++){
        if(!ans[i]&&m) ans[i]=m--;
        printf("%d ",ans[i]);
    }
    puts("");
}