#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define fir first
#define sec second
const int maxn=3e5+10;
const int inf=0x3f3f3f3f;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int n,m;
struct Interval{
    int l,r,id;
    Interval()=default;
    Interval(int l_,int r_,int id_):l(l_),r(r_),id(id_){}
    bool operator<(const Interval &rhs)const{
        if(l==rhs.l) return r<rhs.r;
        else return l<rhs.l;
    }
}p[maxn];
struct Pair{
    Interval A,B;
    Pair()=default;
    Pair(Interval A_,Interval B_):A(A_),B(B_){}
    bool operator<(const Pair &rhs)const{
        return B.r>rhs.B.r;
    }
};
priority_queue<Pair> Q1,Q2;
int ans[maxn];

int main(){
    // freopen("interval.in","r",stdin);
    // freopen("interval.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        p[i].l=read(),p[i].r=read();
        p[i].id=i;
    }
    sort(p+1,p+n+1);
    for(int i=1;i<=n;++i){
        if(!Q1.empty()&&Q1.top().B.r<p[i].l){
            Pair now=Q1.top();
            Q1.pop();
            Q2.push(Pair(now.B,p[i]));
        }
        else{
            if(!Q2.empty()&&Q2.top().B.r<p[i].r){
                Pair now=Q2.top();
                Q2.pop();
                Q1.push(Pair(Interval(0,0,0),now.B));
                now.B=p[i];
                Q2.push(now);
            }
            else Q1.push(Pair(Interval(0,0,0),p[i]));
        }
    }
    for(int i=1,j=1;i<=m;++i){
        if(!Q2.empty()){
            Pair now=Q2.top();
            Q2.pop();
            ans[now.A.id]=i,ans[now.B.id]=i;
        }
        else{
            while(j<=n&&ans[j]) ++j;
            if(j<=n) ans[j]=i;
        }
    }
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}