#include <bits/stdc++.h>
using namespace std;
#define C(Z) lower_bound(xVals, xVals + N, Z) - xVals
#define calc(i, j) max(abs(X[i] - X[j]), abs(Y[i] - Y[j]))
#define int int64_t
const int LIM = 250'000;
int N, K, ext;
int X[LIM], Y[LIM], byY[LIM], xVals[LIM], xPos[LIM];
map<int, int> done[LIM];
bool build(int dist, bool final) {
set<array<int, 2>> on;
for(int i = 0; i < N; ++i)
done[i].clear();
int p = 0, f = 0;
for(int _ = 0; _ < N; ++_) {
int i = byY[_];
while(Y[i] - Y[byY[p]] > dist)
on.erase({X[byY[p]], byY[p]}), ++p;
auto j = on.lower_bound({(X[i] - dist), -1});
bool nxt = 1;
while(j != end(on) && (*j)[0] <= X[i] + dist) {
f += (++done[(*j)[1]][i] < 2);
if(final && calc(i, (*j)[1]) == dist && !--ext) {
--dist;
while(Y[i] - Y[byY[p]] > dist)
on.erase({X[byY[p]], byY[p]}), ++p;
j = on.lower_bound({(X[i] - dist), -1});
nxt = 0;
}
if(!final && f >= K) return 0;
if(nxt) ++j;
nxt = 1;
}
on.insert({X[i], i});
}
return f + 1;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> N >> K;
for(int i = 0, x, y; i < N; ++i) {
cin >> x >> y;
X[i] = x + y;
Y[i] = x - y;
byY[i] = i;
xVals[i] = X[i];
}
sort(byY, byY + N, [&](int &i, int &j) {
return Y[i] < Y[j];
});
sort(xVals, xVals + N);
for(int i = 0; i < N; ++i)
xPos[i] = C(X[i]);
int dist = -1;
for(int b = 1LL<<33, c; b /= 2; ) {
if((c = build(dist + b, 0))) dist += b, ext = K - (c - 1);
}
++dist;
build(dist, 1);
int res[K], p = 0;
for(int i = 0; i < N; ++i)
for(auto [j, _] : done[i])
res[p++] = calc(i, j);
sort(res, res + K);
for(int i : res) cout << i << '\n';
}
