#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint inf = 1e18;
class Fenwick {
public:
int sz;
vector<int> tree;
Fenwick(int sz) : sz(sz), tree(sz, 0) {}
void Update(int p, int x) {
for (int i = p; i < sz; i |= i + 1) {
tree[i] += x;
}
}
int Query(int p) {
int res = 0;
for (int i = p; i > 0; i &= i - 1) {
res += tree[i - 1];
}
return res;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<lint> X(N), Y(N);
vector<lint> coordX = {-inf, inf}, coordY = {-inf, inf};
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
tie(X[i], Y[i]) = make_pair(X[i] + Y[i], X[i] - Y[i]);
coordX.emplace_back(X[i]);
coordY.emplace_back(Y[i]);
}
sort(begin(coordX), end(coordX));
sort(begin(coordY), end(coordY));
coordX.resize(unique(begin(coordX), end(coordX)) - begin(coordX));
coordY.resize(unique(begin(coordY), end(coordY)) - begin(coordY));
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int i, int j) { return X[i] < X[j]; });
const auto Count = [&](lint dist) {
Fenwick F(coordY.size());
const auto Modify = [&](int i, int x) {
int yid = lower_bound(begin(coordY), end(coordY), Y[i]) - begin(coordY);
F.Update(yid, x);
};
lint res = 0;
for (int i = 0, j = 0; i < N; i++) {
while (abs(X[ord[i]] - X[ord[j]]) > dist) Modify(ord[j++], -1);
int ylo = lower_bound(begin(coordY), end(coordY), Y[ord[i]] - dist) - begin(coordY);
int yhi = upper_bound(begin(coordY), end(coordY), Y[ord[i]] + dist) - begin(coordY);
res += F.Query(yhi) - F.Query(ylo);
Modify(ord[i], 1);
}
return res;
};
const auto Generate = [&](lint dist) -> vector<lint> {
set<pair<lint, int>> F;
const auto Modify = [&](int i, int x) {
if (x == 1) {
F.emplace(Y[i], i);
} else if (x == -1) {
F.erase({Y[i], i});
}
};
vector<pair<int, int>> pairs;
for (int i = 0, j = 0; i < N; i++) {
while (abs(X[ord[i]] - X[ord[j]]) > dist) Modify(ord[j++], -1);
int ylo = lower_bound(begin(coordY), end(coordY), Y[ord[i]] - dist) - begin(coordY);
int yhi = upper_bound(begin(coordY), end(coordY), Y[ord[i]] + dist) - begin(coordY);
auto it = F.lower_bound({Y[ord[i]] - dist, -1});
while (it != end(F) && abs(it->first - Y[ord[i]]) <= dist) {
pairs.emplace_back(ord[i], it->second);
it++;
}
Modify(ord[i], 1);
}
vector<lint> res;
for (auto [i, j] : pairs) {
if (i != j) {
res.emplace_back(max(abs(X[i] - X[j]), abs(Y[i] - Y[j])));
}
}
return res;
};
lint lo = 0, hi = 1e10;
while (lo < hi) {
lint md = (lo + hi) / 2;
if (Count(md) >= K) {
hi = md;
} else {
lo = md + 1;
}
}
vector<lint> ans = Generate(lo - 1);
while (ans.size() < K) {
ans.emplace_back(lo);
}
sort(begin(ans), end(ans));
assert(ans.size() == K);
for (int i = 0; i < K; i++) {
cout << ans[i] << '\n';
}
return 0;
}
