#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using ll=long long;int n,k;int x[250007],y[250007];int X[250007],Y[250007];int N,M;int ls[10000007],rs[10000007],sz[10000007],nodecnt;void build(int p,int l,int r){if(l==r){return;}int mid=(l+r)>>1;build(ls[p]=++nodecnt,l,mid),build(rs[p]=++nodecnt,mid+1,r);}void modify(int p,int np,int l,int r,int i,int d){if(l==r){sz[np]=sz[p]+d;return;}int mid=(l+r)>>1;if(i<=mid){ls[np]=++nodecnt;rs[np]=rs[p];modify(ls[p],ls[np],l,mid,i,d);sz[np]=sz[ls[np]]+sz[rs[np]];return;}ls[np]=ls[p];rs[np]=++nodecnt;modify(rs[p],rs[np],mid+1,r,i,d);sz[np]=sz[ls[np]]+sz[rs[np]];}int query(int p,int q,int l,int r,int ql,int qr){if(ql<=l&&r<=qr){return sz[p]-sz[q];}int mid=(l+r)>>1;int res=0;if(ql<=mid){res=query(ls[p],ls[q],l,mid,ql,qr)+res;}if(qr>mid){res=res+query(rs[p],rs[q],mid+1,r,ql,qr);}return res;}int root[500007];int ffg(int*a,int s,ll x){return std::lower_bound(a+1,a+s+1,x)-a;}int fll(int*a,int s,ll x){return std::upper_bound(a+1,a+s+1,x)-a-1;}void build(){for(int i=1;i<=n;++i){X[++N]=x[i],Y[++M]=y[i];}std::sort(X+1,X+N+1),N=std::unique(X+1,X+N+1)-X-1;std::sort(Y+1,Y+M+1),M=std::unique(Y+1,Y+M+1)-Y-1;std::vector<std::pair<int,int>>v;for(int i=1;i<=n;++i){v.push_back({x[i],y[i]});}std::sort(v.begin(),v.end());n=0;for(auto[xx,yy]:v){++n,x[n]=xx,y[n]=yy;}build(root[0]=++nodecnt,1,M);for(int i=1;i<=n;++i){modify(root[i-1],root[i]=++nodecnt,1,M,ffg(Y,M,y[i]),+1);}}int query(int i,ll d){int yl=ffg(Y,M,y[i]-d),yr=fll(Y,M,y[i]+d);if(!(1<=yl&&yl<=yr&&yr<=M)){return 0;}int xl=fll(x,n,x[i]-d-1);return query(root[i],root[xl],1,M,yl,yr);}ll nxt[250007],RRR[250007];int lecnt[250007],ecnt[250007];void getnxt(int i){ll l=nxt[i]+1,r=RRR[i],res=-1;int newlecnt=-1;std::vector<std::pair<ll,int>>t;while(l<=r){ll mid=(l+r)>>1;int p=query(i,mid);if(p>lecnt[i]){newlecnt=p;r=(res=mid)-1;}else{l=mid+1;}t.push_back({mid,p});}RRR[i]=4e9;for(auto[j,val]:t){if(val>newlecnt){RRR[i]=std::min(RRR[i],j);}}nxt[i]=res,ecnt[i]=newlecnt-lecnt[i],lecnt[i]=newlecnt;}ll ans[250007],top;int main(){std::cin>>n>>k;for(int i=1;i<=n;++i){int xx,yy;std::cin>>xx>>yy;x[i]=xx+yy,y[i]=xx-yy;}build();std::priority_queue<std::pair<ll,int>>q;for(int i=1;i<=n;++i){nxt[i]=0,lecnt[i]=ecnt[i]=1;RRR[i]=4e9;getnxt(i);if(nxt[i]!=-1){q.push({-nxt[i],i});}}while(!q.empty()){int i=q.top().second;q.pop();int t=ecnt[i];while(top<k&&t--){ans[++top]=nxt[i];}if(top==k){break;}getnxt(i);if(nxt[i]!=-1){q.push({-nxt[i],i});}}for(int i=1;i<=k;++i){std::cout<<ans[i]<<'\n';}return 0;}