#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll N,K; const ll INF = 1e18;
vector<pii> vtwn;
vector<ll> dlog; //distance log
set<pii> s0; //set of currently active
//{y,x}
bool test(ll D0) { //if >=K roads with distance <=D0 -> return 1
dlog.clear();
s0.clear();
for (pii pt: vtwn) {
if (dlog.size()>=K) {
return 1;
}
ll x = pt.first; ll y = pt.second;
vector<pii> vdel; //vector to delete
auto A0 = s0.lower_bound({y-D0,-INF});
while (A0!=s0.end() && ((*A0).first<=y+D0) && dlog.size()<K) {
pii p0 = *A0;
ll y0 = p0.first; ll x0 = p0.second;
ll d0 = llabs(y-y0)+llabs(x-x0);
if (d0<=D0) {
dlog.push_back(d0);
}
if ((x-x0)>D0) {
vdel.push_back(p0);
}
A0++;
}
for (pii p0: vdel) {
s0.erase(p0);
}
s0.insert({y,x});
}
return (dlog.size()>=K);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> K;
for (ll i=0;i<N;i++) {
ll x,y; cin >> x >> y;
vtwn.push_back({x,y});
}
sort(vtwn.begin(),vtwn.end());
ll Dmin = 0;
ll Dmax = 4e9+5;
while (Dmin != Dmax) {
ll Dt = (Dmin+Dmax+1)/2;
if (test(Dt)) {
Dmax = Dt-1;
} else {
Dmin = Dt;
}
}
test(Dmin);
ll M = dlog.size();
for (ll i=0;i<(K-M);i++) {
dlog.push_back(Dmin+1);
}
sort(dlog.begin(),dlog.end());
for (ll x: dlog) {
cout << x << "\n";
}
}
