#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=3e5;

int n,m,s,mch[Maxn+5],ans[Maxn+5];
struct Data{int k,a,b;}; array<int,3> h[Maxn+5];
inline bool operator<(Data x,Data y) {return x.k>y.k;}

int main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m;
    For(i,1,n) cin>>h[i][0]>>h[i][1],h[i][2]=i;
    sort(h+1,h+n+1); priority_queue<Data> q1,q2;
    For(_,1,n)
    {
        auto [l,r,id]=h[_];
        if(!q1.empty() && q1.top().k<l)
        {
            int p=q1.top().a; q1.pop();
            mch[p]=id,mch[id]=p,q2.push(Data{r,p,id});
        }
        else if(!q2.empty() && q2.top().k<l)
        {
            auto [k,a,b]=q2.top(); q2.pop();
            mch[a]=id,mch[id]=a,mch[b]=0;
            q2.push(Data{r,a,id}),q1.push(Data{k,b,0});
        } else q1.push(Data{r,id,0});
    }
    For(i,1,n) if(mch[i] && !ans[i] && s<m) ++s,ans[i]=ans[mch[i]]=s;
    For(i,1,n) if(!ans[i] && s<m) ans[i]=++s;
    For(i,1,n) printf("%d ",ans[i]); printf("\n");
    return 0;
}