#include <bits/stdc++.h>
using namespace std;
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<pair<int64_t, int64_t>> a(n);
vector<int64_t> buff_x, buff_y;
for (auto &[x, y] : a) {
int64_t px, py;
cin >> px >> py;
x = px + py, y = px - py;
buff_x.push_back(x), buff_y.push_back(y);
}
sort(a.begin(), a.end());
sort(buff_x.begin(), buff_x.end());
sort(buff_y.begin(), buff_y.end());
buff_x.erase(unique(buff_x.begin(), buff_x.end()), buff_x.end());
buff_y.erase(unique(buff_y.begin(), buff_y.end()), buff_y.end());
auto comp_x_lb = [&](int64_t x) { return lower_bound(buff_x.begin(), buff_x.end(), x) - buff_x.begin(); };
auto comp_x_ub = [&](int64_t x) { return upper_bound(buff_x.begin(), buff_x.end(), x) - buff_x.begin() - 1; };
auto comp_y_lb = [&](int64_t y) { return lower_bound(buff_y.begin(), buff_y.end(), y) - buff_y.begin(); };
auto comp_y_ub = [&](int64_t y) { return upper_bound(buff_y.begin(), buff_y.end(), y) - buff_y.begin() - 1; };
vector<vector<pair<int, int>>> seg(2 * buff_x.size());
for (int i = 0; i < n; ++i) {
seg[buff_x.size() + comp_x_lb(a[i].first)].emplace_back(comp_y_lb(a[i].second), i);
}
for (auto &i : seg) {
sort(i.begin(), i.end());
}
for (int i = buff_x.size() - 1; i >= 1; --i) {
seg[i].resize(seg[2 * i].size() + seg[2 * i + 1].size());
merge(seg[2 * i].begin(), seg[2 * i].end(), seg[2 * i + 1].begin(), seg[2 * i + 1].end(), seg[i].begin());
}
auto count_in = [&](int idx, int ly, int ry) {
pair<int, int> p2 = {ry, n}, p1 = {ly, -1};
return int(upper_bound(seg[idx].begin(), seg[idx].end(), p2) - lower_bound(seg[idx].begin(), seg[idx].end(), p1));
};
auto in_rect = [&](int64_t lx, int64_t rx, int64_t ly, int64_t ry) {
int64_t ans = 0;
lx = comp_x_lb(lx), ly = comp_y_lb(ly), rx = comp_x_ub(rx), ry = comp_y_ub(ry);
for (lx += buff_x.size(), rx += buff_x.size() + 1; lx < rx; lx >>= 1, rx >>= 1) {
if (lx & 1) {
ans += count_in(lx++, ly, ry);
}
if (rx & 1) {
ans += count_in(--rx, ly, ry);
}
}
return ans;
};
auto iterate = [&](int idx, int ly, int ry, vector<int> &res) {
pair<int, int> p2 = {ry, n}, p1 = {ly, -1};
for (auto it = lower_bound(seg[idx].begin(), seg[idx].end(), p1), it2 = upper_bound(seg[idx].begin(), seg[idx].end(), p2); it != it2; ++it) {
res.push_back(it->second);
}
};
auto iterate_rect = [&](int64_t lx, int64_t rx, int64_t ly, int64_t ry) {
lx = comp_x_lb(lx), ly = comp_y_lb(ly), rx = comp_x_ub(rx), ry = comp_y_ub(ry);
vector<int> res;
for (lx += buff_x.size(), rx += buff_x.size() + 1; lx < rx; lx >>= 1, rx >>= 1) {
if (lx & 1) {
iterate(lx++, ly, ry, res);
}
if (rx & 1) {
iterate(--rx, ly, ry, res);
}
}
return res;
};
int64_t dist = *ranges::partition_point(views::iota(int64_t(1), int64_t(4e9) + 1), [&](int64_t dist) {
int64_t ans = 0;
for (auto &[x, y] : a) {
ans += in_rect(x - dist, x + dist, y - dist, y + dist);
}
return (ans - n) / 2 < k;
}) - 1;
vector<int64_t> dists;
for (auto &[x, y] : a) {
vector<int> res = iterate_rect(x - dist, x + dist, y - dist, y + dist);
for (int &i : res) {
dists.push_back(max(abs(x - a[i].first), abs(y - a[i].second)));
}
}
sort(dists.begin(), dists.end());
for (int i = n, j = 0; j < k; i += 2, ++j) {
cout << (i < dists.size() ? dists[i] : dist + 1) << '\n';
}
}
