#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii, int> iii;
int n, k;
int x[250005], y[250005];
vector<iii> P;
vector<int> ys;
int fw[250005];
void up(int x, int nv){
while (x <= 250000){
fw[x] += nv;
x += x&-x;
}
}
int qu(int x){
int ret = 0;
while (x){
ret += fw[x];
x -= x&-x;
}
return ret;
}
inline int lb(int y){
return lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
}
inline int ub(int y){
return upper_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
}
int test(int D){
int c = 0;
int ret = 0;
for (auto it : P){
int X = it.fi.fi, Y = it.fi.se;
while (c < P.size() && P[c].fi.fi <= X + D){
up(lb(P[c].fi.se), 1);
c++;
}
up(lb(Y), -1);
ret += qu(ub(Y + D) - 1) - qu(lb(Y-D) - 1);
///printf("%d %d %d\n",X,Y,id);
}
///printf("%lld %lld\n",D,ret);
return ret;
}
vector<int> solve(int D){
int c = 0;
vector<int> ret;
set<ii> S;
for (auto it : P){
int X = it.fi.fi, Y = it.fi.se, id = it.se;
while (c < P.size() && P[c].fi.fi <= X + D){
S.insert({lb(P[c].fi.se), P[c].se});
c++;
}
S.erase({lb(Y), id});
for (auto it = S.lower_bound({lb(Y-D), -1}); it != S.end() && it != S.upper_bound({ub(Y+D),-1}); it++){
int idx = it->se;
ret.push_back(abs(x[idx] - x[id]) + abs(y[idx] - y[id]));
}
///printf("%d %d %d\n",X,Y,id);
}
///printf("%lld %lld\n",D,ret);
return ret;
}
main(){
scanf("%lld%lld",&n,&k);
for (int i = 0; i < n; i++){
scanf("%lld%lld",&x[i],&y[i]);
int nx = x[i]+y[i];
int ny = x[i]-y[i];
ys.push_back(ny);
P.push_back({{nx, ny}, i});
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
sort(P.begin(), P.end());
int lo = 0, hi = 4000000000ll;
while (lo < hi){
int mid = (lo+hi)/2;
if (test(mid) < k) lo = mid+1;
else hi = mid;
}
vector<int> ans = solve(lo);
sort(ans.begin(), ans.end());
for (int i = 0; i < k; i++){
printf("%lld\n",ans[i]);
}
}
