#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 250000 + 6;
ll X[N], Y[N];
int p[N];
int n, k, x[N], y[N];
vector<ll>xs,ys;
int F[N];
void upd(int pos, int v) {
while (pos < N) {
F[pos] += v;
pos |= pos + 1;
}
}
int get(int pos) {
int r = 0;
while (pos >= 0) {
r += F[pos];
pos &= pos + 1, pos--;
}
return r;
}
bool check(ll M) {
int res = 0;
int l = 1;
for (int i = 0 ; i < N ; ++ i) F[i] = 0;
for (int i = 1 ; i <= n ; ++ i) {
while (l < i && X[p[i]] - X[p[l]] >= M) {
upd(y[p[l]], -1);
l++;
}
int sx = lower_bound(ys.begin(), ys.end(), Y[p[i]] - M + 1) - ys.begin();
int ex = upper_bound(ys.begin(), ys.end(), Y[p[i]] + M - 1) - ys.begin() - 1;
res += get(ex) - get(sx - 1);
if (res >= k) break;
upd(y[p[i]], +1);
}
while (l <= n) upd(y[p[l]], -1), ++l;
return res >= k;
}
vector<ll>ANS;
void restore(ll M) {
set<pair<ll,ll>>S = {{Y[p[1]], X[p[1]]}};
int l = 1;
for (int i = 2 ; i <= n ; ++ i) {
while (l < i && X[p[i]] - X[p[l]] >= M) {
S.erase({Y[p[l]], X[p[l]]});
l++;
}
auto st = S.lower_bound(pair{Y[p[i]] - M + 1, -1e10});
for (; st != S.end() ; ++ st) {
if (max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])) < M) {
ANS.emplace_back(max(abs(st->first - Y[p[i]]), abs(st->second - X[p[i]])));
} else break;
}
S.insert({Y[p[i]], X[p[i]]});
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1 ; i <= n ; ++ i) {
ll a, b;
cin >> a >> b;
X[i] = a + b, Y[i] = a - b;
xs.emplace_back(X[i]), ys.emplace_back(Y[i]);
}
sort(xs.begin(), xs.end()); xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
for (int i = 1 ; i <= n ; ++ i) {
x[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
y[i] = lower_bound(ys.begin(), ys.end(), Y[i]) - ys.begin();
}
for (int i = 1 ; i <= n ; ++ i) {
p[i] = i;
}
sort(p + 1, p + 1 + n, [](int i, int j) {
return X[i] < X[j];
});
ll L = 1, R = ll(1e10);
ll ans = -1;
while (L <= R) {
ll M = (L + R) / 2;
int res = check(M);
if (!res) { // ? < k
ans = M;
L = M + 1;
} else {
R = M - 1;
}
}
assert(ans != -1);
restore(ans);
sort(ANS.begin(), ANS.end());
for (ll i : ANS) cout << i << endl;;
int cnt = ANS.size();
for (; cnt < k ; ++cnt) {
cout << ans << "\n";
}
cout << endl;
}
