#include <bits/stdc++.h>
using namespace std;
#define C(Z) lower_bound(xVals, xVals + N, Z) - xVals
#define int int64_t
int N, K, F[250'001];
void add(int i, int v) {
for(i++; i <= N; i += i&-i) F[i] += v;
}
int get(int i, int v = 0) {
for(i++; i >= 1; i -= i&-i) v += F[i];
return v;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> N >> K;
int X[N], Y[N], byY[N], xVals[N], xPos[N];
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, ext;
for(int b = 1LL<<33; b /= 2; ) {
dist += b;
int f = 0;
int p = 0;
fill(F, F + N + 1, 0);
for(int i : byY) {
while(Y[i] - Y[byY[p]] > dist)
add(xPos[byY[p++]], -1);
f += get(C(X[i] + dist + 1)-1);
f -= get(C(X[i] - dist + 0)-1);
add(xPos[i], 1);
}
if(f >= K) dist -= b;
else ext = K - f;
}
++dist;
set<array<int, 2>> on;
priority_queue<int> ans;
map<int, int> done[N];
int p = 0;
for(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) {
int o = (*j)[1];
int r = max(abs(X[i] - X[o]), Y[i] - Y[o]);
if(r == 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(++done[o][i] < 2) ans.push(-r);
if(nxt) ++j;
nxt = 1;
}
on.insert({X[i], i});
}
while(!empty(ans))
cout << -ans.top() << '\n', ans.pop();
}
