#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const
namespace IO{
inline char gc(){
static cs int Rlen=1<<22|1;
static char buf[Rlen],*p1,*p2;
return p1p2&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1p2)?EOF:*p1++;
}
template<typename T>
inline T get(){
char c;T num;
while(!isdigit(c=gc()));num=c^48;
while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
return num;
}
inline int gi(){return get<int>();}
inline ll gl(){return get<ll>();}
}
using namespace IO;
using stdcerr;
using stdcout;
using pli=std::pair<ll,int>;
#define fi first
#define se second
cs int N=1e5+7;
struct frac{
ll a,b,c;//a + b/c (c>0,b>0)
frac(){a=b=0,c=1;}
frac(ll x,ll y){
if(y<0)x=-x,y=-y;
a=x/y,c=y,b=x%y;
if(b<0)b+=c,--a;
}
ll flr()cs{return a;}
ll cel()cs{return a+(b>0);}
bool operator<(cs frac &x)cs{return ax.a?bx.c<x.bc:a<x.a;}
bool operator<=(cs frac &x)cs{return ax.a?bx.c<=x.bc:a<=x.a;}
};
int n,m,ct,tp;
int id[N],st[N],ans[N];
ll a[N],b[N];frac x[N];
pli q[N<<1];
inline frac gx(int x,int y){
return frac(b[x]-b[y],a[y]-a[x]);
}
inline void solve(int k){
ct=tp=0;x[0]=frac(0,1);
for(int re i=1;i<=n;i)if(-1ans[id[i]]&&a[id[i]]>a[st[tp]]){
int u=id[i];
while(tp&&gx(u,st[tp]).flr()<x[tp].cel())--tp;
st[++tp]=u;if(tp>1)x[tp]=gx(u,st[tp-1]);
}
x[tp+1]=frac(1ll<<60,1);
for(int re i=1;i<=n;++i)if(~ans[i]){
int l=1,r=tp-1,t=tp;
while(l<=r){
int mid=l+r>>1;
if(a[st[mid]]>=a[i]||gx(st[mid],i)<=x[mid+1])t=mid,r=mid-1;
else l=mid+1;
}
q[++ct]=pli(a[st[t]]>=a[i]?0ll:gx(st[t],i).flr()+1,1);
l=2,r=tp,t=1;
while(l<=r){
int mid=l+r>>1;
if(a[st[mid]]<=a[i]||x[mid]<=gx(st[mid],i))t=mid,l=mid+1;
else r=mid-1;
}
if(a[st[t]]>a[i])q[++ct]=pli(gx(st[t],i).cel(),-1);
}
std::sort(q+1,q+ct+1);
for(int re i=1,j=1,p=0;i<=tp;i){
while(j<=ct&&q[j].fi<=x[i].cel())p+=q[j].se;
if(p<k)ans[st[i]]=k;
while(j<=ct&&q[j].fi<=x[i+1].flr()){
int l=j;while(l<=ct&&q[l].fiq[j].fi)p+=q[l].se;
if(p<k)ans[st[i]]=k;j=l;
}
}
}
signed main(){
#ifdef zxyoi
freopen("ZJOI.in","r",stdin);
#endif
n=gi(),m=gi();
for(int re i=1;i<=n;++i)
a[i]=gl(),b[i]=gl(),id[i]=i,ans[i]=-1;
std::sort(id+1,id+n+1,[](int x,int y){
return a[x]<a[y]||(a[x]==a[y]&&b[x]>b[y]);
});
for(int re i=1;i<=m;++i)solve(i);
for(int re i=1;i<=n;++i)cout<<ans[i]<<" ";
return 0;
}
