#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> yvs;
vector<int> xvs;
int fenw[250005];
void upd(int pos, int v){
pos++;
while (pos<250005){
fenw[pos]+=v;
pos += pos&-pos;
}
}
int qu(int pos){
pos++;
int ans = 0;
while (pos>0){
ans += fenw[pos];
pos -= pos&-pos;
}
return ans;
}
int origX[250005];
int origY[250005];
int nX[250005];
int nY[250005];
vector<pair<pair<int,int>,int>> pts;
int lb(int v){
return lower_bound(yvs.begin(),yvs.end(),v)-yvs.begin();
}
int ub(int v){
return upper_bound(yvs.begin(),yvs.end(),v)-yvs.begin();
}
int check(int dist){
for (int x = 0; x<250005; x++) fenw[x] = 0;
int c = 0;
int ans = 0;
for (auto x : pts){
while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
upd(lb(pts[c].first.second),1);
c++;
}
upd(lb(x.first.second),-1);
ans += qu(ub(x.first.second+dist)-1)-qu(lb(x.first.second-dist)-1);
}
return ans;
}
vector<pair<int,int> > getall(int dist){
int c = 0;
vector<pair<int,int> > ans;
set<pair<int,int> > stuff;
for (auto x : pts){
while (c<pts.size() && pts[c].first.first<=x.first.first+dist){
stuff.insert({pts[c].first.second,pts[c].second});
//printf("ins %lld\n",c);
c++;
}
stuff.erase({x.first.second,x.second});
//printf("er %lld\n",x.second);
for (auto it = stuff.lower_bound({x.first.second-dist,-1}); (it!=stuff.end()) && (*it).first<=x.first.second+dist; it++){
ans.push_back({x.second,(*it).second});
assert(x.second!=(*it).second);
}
}
return ans;
}
int md(pair<int,int> x){
return abs(origX[x.first]-origX[x.second])+abs(origY[x.first]-origY[x.second]);
}
bool cmp(pair<int,int> a,pair<int,int>b){
return md(a)<md(b);
}
main(){
int n,K;
scanf("%lld%lld",&n,&K);
for (int x = 0; x<n; x++){
scanf("%lld%lld",&origX[x],&origY[x]);
nX[x] = origX[x]+origY[x];
nY[x] = origY[x]-origX[x];
pts.push_back({{nX[x],nY[x]},x});
yvs.push_back(nY[x]);
}
sort(pts.begin(),pts.end());
sort(yvs.begin(),yvs.end());
int l = 0;
int r = 4000000000LL;
while (l+1<r){
int mid = (l+r)/2;
if (check(mid)>=K){
r = mid;
}
else l = mid;
}
vector<pair<int,int>> impt = getall(l);
sort(impt.begin(),impt.end(),cmp);
for (auto x : impt){
printf("%lld\n",abs(origX[x.first]-origX[x.second])+abs(origY[x.first]-origY[x.second]));
}
for (int x = impt.size(); x<K; x++){
printf("%lld\n",r);
}
}
