#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll
const ll inf = 1e10;
const int mxn = 250005;
int N,K;
ll bit[mxn*2];
pll arr[mxn];
vector<ll> all;
vector<int> ans;
struct Q{
int tp;
ll l,r;
ll x,id;
Q(){}
Q(ll tt,ll xx,ll s,ll e,ll ii = 0){
tp = tt,x = xx,l = s,r = e;
id = ii;
}
bool operator<(Q &b)const{
return x == b.x?tp<b.tp:x<b.x;
}
};
vector<Q> op;
void modify(int p,ll v){
for(;p<mxn*2;p+=p&-p)bit[p] += v;
return;
}
ll getval(ll p){
ll re = 0;
for(;p>0;p-= p&-p)re += bit[p];
return re;
}
inline ll calc(ll len){
memset(bit,0,sizeof(bit));
op.clear();
for(int i = 1;i<=N;i++){
ll tl = arr[i].sc-len,tr = arr[i].sc+len;
tl = lower_bound(all.begin(),all.end(),tl)-all.begin();
tr = upper_bound(all.begin(),all.end(),tr)-all.begin();
ll tmp = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
op.push_back(Q(0,arr[i].fs-len,tl,tr));
op.push_back(Q(-1,arr[i].fs+len+1,tl,tr));
op.push_back(Q(1,arr[i].fs,tmp,tmp));
}
ll re = 0;
sort(op.begin(),op.end());
for(auto &i:op){
if(i.tp == 0){
modify(i.l,1);
modify(i.r,-1);
}
else if(i.tp == -1){
modify(i.l,-1);
modify(i.r,1);
}
else{
re += getval(i.l);
}
}
assert((re-N)%2 == 0);
return (re-N)/2;
}
set<int> segtree[mxn*4];
void addval(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
if(v>0)segtree[now].insert(v);
else segtree[now].erase(-v);
return;
}
int mid = (l+r)>>1;
if(mid>=s)addval(now*2+1,l,mid,s,e,v);
if(mid<e)addval(now*2+2,mid+1,r,s,e,v);
return;
}
void getp(int now,int l,int r,int p,int id){
for(auto &i:segtree[now]){
if(id>=i)continue;
ans.push_back(max(abs(arr[id].fs-arr[i].fs),abs(arr[id].sc-arr[i].sc)));
}
if(l == r)return;
int mid = (l+r)>>1;
if(mid>=p)getp(now*2+1,l,mid,p,id);
else getp(now*2+2,mid+1,r,p,id);
return;
}
void getans(int len){
op.clear();
for(int i = 1;i<=N;i++){
ll tl = arr[i].sc-len,tr = arr[i].sc+len;
tl = lower_bound(all.begin(),all.end(),tl)-all.begin();
tr = upper_bound(all.begin(),all.end(),tr)-all.begin();
ll tmp = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
op.push_back(Q(0,arr[i].fs-len,tl,tr,i));
op.push_back(Q(-1,arr[i].fs+len+1,tl,tr,i));
op.push_back(Q(1,arr[i].fs,tmp,tmp,i));
}
sort(op.begin(),op.end());
for(auto &i:op){
if(i.tp == 0)addval(0,0,all.size(),i.l,i.r-1,i.id);
else if(i.tp == -1)addval(0,0,all.size(),i.l,i.r-1,-i.id);
else getp(0,0,all.size(),i.l,i.id);
}
return;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>K;
for(int i = 1;i<=N;i++){
cin>>arr[i].fs>>arr[i].sc;
arr[i] = make_pair(arr[i].fs+arr[i].sc,-arr[i].fs+arr[i].sc);
all.push_back(arr[i].sc);
}
//for(int i =1;i<=N;i++)cout<<arr[i].fs<<','<<arr[i].sc<<' ';cout<<endl;
all.push_back(-inf);
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
ll l = 1,r = 4e9;
while(l != r){
ll mid = (l+r)>>1;
if(calc(mid)>=K)r = mid;
else l = mid+1;
}
//cout<<"MAX:"<<l<<' '<<calc(l)<<endl;
getans(l-1);
//for(auto &i:ans)cout<<i<<',';cout<<endl;
while(ans.size()<K)ans.push_back(l);
sort(ans.begin(),ans.end());
for(auto &i:ans)cout<<i<<'\n';
return 0;
}
