#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;
map<pii,int> mp;
pii p[maxn];
struct Pair{
    pii A,B;
    Pair()=default;
    Pair(pii A_,pii B_):A(A_),B(B_){}
    bool operator<(const Pair &rhs)const{
        return B.sec>rhs.B.sec;
    }
};
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].fir=read(),p[i].sec=read();
        mp[p[i]]=i;
    }
    sort(p+1,p+n+1);
    for(int i=1;i<=n;++i){
        if(!Q1.empty()&&Q1.top().B.sec<p[i].fir){
            Pair now=Q1.top();
            Q1.pop();
            Q2.push(Pair(now.B,p[i]));
        }
        else{
            if(!Q2.empty()&&Q2.top().B.sec<p[i].sec){
                Pair now=Q2.top();
                Q2.pop();
                Q1.push(Pair(make_pair(0,0),now.B));
                now.B=p[i];
                Q2.push(now);
            }
            else Q1.push(Pair(make_pair(0,0),p[i]));
        }
    }
    for(int i=1,j=1;i<=m;++i){
        if(!Q2.empty()){
            Pair now=Q2.top();
            Q2.pop();
            ans[mp[now.A]]=i,ans[mp[now.B]]=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;
}