//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,k;
llo aa[300001];
llo bb[300001];
pair<llo,llo> tree[30*600001];
llo ll[30*700001];
llo rr[30*700001];
pair<llo,llo> le[300001];
llo mm[3000001];
pair<llo,llo> re[300001];
llo nn[3000001];
vector<pair<llo,llo>> ss;
llo cur=0;
llo build(llo l,llo r){
llo cot=cur;
cur++;
if(l==r){
tree[cot]={(llo)1e18,l};
return cot;
}
else{
llo mid=(l+r)/2;
ll[cot]=build(l,mid);
rr[cot]=build(mid+1,r);
if(tree[ll[cot]].a<=tree[rr[cot]].a){
tree[cot]=tree[ll[cot]];
}
else{
tree[cot]=tree[rr[cot]];
}
return cot;
}
}
llo update(llo no,llo l,llo r,llo i,llo val){
llo cot=cur;
cur++;
if(l==r){
tree[cot]={val,l};
}
else{
ll[cot]=ll[no];
rr[cot]=rr[no];
llo mid=(l+r)/2;
if(i<=mid){
ll[cot]=update(ll[cot],l,mid,i,val);
}
else{
rr[cot]=update(rr[cot],mid+1,r,i,val);
}
if(tree[ll[cot]].a<=tree[rr[cot]].a){
tree[cot]=tree[ll[cot]];
}
else{
tree[cot]=tree[rr[cot]];
}
}
return cot;
}
pair<llo,llo> query(llo no,llo l,llo r,llo aa,llo bb){
if(aa>bb or r<aa or l>bb){
return {1e18,-1};
}
else if(aa<=l and r<=bb){
return tree[no];
}
else{
llo mid=(l+r)/2;
pair<llo,llo> xx=query(ll[no],l,mid,aa,bb);
pair<llo,llo> yy=query(rr[no],mid+1,r,aa,bb);
if(xx.a<=yy.a){
return xx;
}
else{
return yy;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k;
for(llo i=0;i<n;i++){
cin>>aa[i];
cin>>bb[i];
ss.pb({aa[i],-bb[i]});
}
sort(ss.begin(),ss.end());
for(int i=0;i<ss.size();i++){
ss[i].b=-ss[i].b;
}
/*vector<int> tt;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
tt.pb(abs(aa[i]-aa[j])+abs(bb[i]-bb[j]));
}
}
sort(tt.begin(),tt.end());*/
/*for(int i=0;i<n;i++){
cout<<ss[i].a<<","<<ss[i].b<<endl;
}*/
/*for(int i=0;i<k;i++){
cout<<tt[i]<<" ";
}
cout<<endl;*/
map<llo,llo> ind3;
for(llo i=0;i<n;i++){
ind3[ss[i].a]=i;
}
llo r1=build(0,n-1);//-x+y
llo r2=build(0,n-1);//x+y;
vector<pair<pair<llo,llo>,llo>> yy;
for(llo i=0;i<n;i++){
yy.pb({{-ss[i].b,ss[i].a},i});
}
sort(yy.begin(),yy.end());
for(int j=0;j<yy.size();j++){
yy[j].a.a=-yy[j].a.a;
}
vector<pair<pair<llo,llo>,llo>> root;
root.pb({{r1,r2},((llo)1e18)});
map<llo,llo> ind;
map<llo,llo> ind2;
llo co=0;
for(auto j:yy){
co++;
r1=update(r1,0,n-1,j.b,-j.a.b+j.a.a);
// cout<<j.b<<"<<"<<-j.a.b+j.a.a<<endl;
r2=update(r2,0,n-1,j.b,j.a.b+j.a.a);
root.pb({{r1,r2},j.a.a});
if(ind.find(j.a.a)==ind.end()){
ind[j.a.a]=co;
}
ind2[j.a.a]=co;
}
/*for(auto j:root){
cout<<j.a.a<<",,"<<j.a.b<<",,"<<j.b<<endl;
}
cout<<endl;*/
//cout<<ind2[2]<<endl;
priority_queue<pair<llo,llo>> xx;
llo xy=0;
/*for(auto j:yy){
cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
}
cout<<endl;*/
for(auto j:yy){
le[xy]=query(root[ind2[j.a.a]].a.a,0,n-1,0,j.b-1);
le[xy].a+=j.a.b-j.a.a;;
mm[xy]=root[ind2[j.a.a]].a.a;
re[xy]=query(root[ind[j.a.a]-1].a.b,0,n-1,ind3[j.a.b]+1,n-1);
re[xy].a-=(j.a.a+j.a.b);
nn[xy]=root[ind[j.a.a]-1].a.b;
//cout<<j.a.a<<","<<j.a.b<<":"<<j.b<<endl;
//cout<<ind2[j.a.a]<<"::"<<0<<"::"<<j.b-1<<endl;
// cout<<le[xy].a<<":"<<re[xy].a<<endl;
// cout<<le[xy].b<<"<<"<<endl;
//cout<<endl;
xx.push({-min(re[xy].a,le[xy].a),xy});
xy++;
}
for(int i=0;i<k;i++){
pair<llo,llo> no=xx.top();
xx.pop();
cout<<(-no.a)<<endl;
xy=no.b;
pair<pair<llo,llo>,llo> j=yy[no.b];
if(le[no.b].a<=re[no.b].a){
/*if(le[no.b].b==-1){
while(true){
continue;
}
}*/
//cout<<11<<endl;
mm[xy]=update(mm[xy],0,n-1,le[xy].b,(llo)1e18);
le[xy]=query(mm[xy],0,n-1,0,j.b-1);
le[xy].a+=j.a.b-j.a.a;;
//cout<<le[xy].a<<"<<"<<endl;
}
else{
/*if(re[no.b].b==-1){
while(true){
continue;
}
}*/
//cout<<11<<endl;
nn[xy]=update(nn[xy],0,n-1,re[xy].b,(llo)1e18);
re[xy]=query(nn[xy],0,n-1,ind3[j.a.b]+1,n-1);
re[xy].a-=(j.a.a+j.a.b);
}
//cout<<no.b<<":"<<re[no.b].a<<":"<<le[j.b].a<<endl;
xx.push({-min(re[no.b].a,le[no.b].a),xy});
}
return 0;
}
