#include <bits/stdc++.h>
using namespace std;
class ordered_set {
struct node {
vector<int> idxs;
node *l, *r;
node() : l(nullptr), r(nullptr) {}
~node() {
delete l;
delete r;
}
};
node *t;
int tl, tr;
void insert(node *t, int tl, int tr, int x, int idx) {
if (x < tl || tr < x) {
return;
}
t->idxs.push_back(idx);
if (tl == tr) {
return;
}
int tm = (tl + tr) / 2;
if (x <= tm) {
insert(t->l = t->l ? t->l : new node(), tl, tm, x, idx);
} else {
insert(t->r = t->r ? t->r : new node(), tm + 1, tr, x, idx);
}
}
int count_in(node *t, int tl, int tr, int l, int r) {
if (!t || r < tl || tr < l) {
return 0;
}
if (l <= tl && tr <= r) {
return t->idxs.size();
}
int tm = (tl + tr) / 2;
return count_in(t->l, tl, tm, l, r) + count_in(t->r, tm + 1, tr, l, r);
}
void iterate(node *t, int tl, int tr, int l, int r, vector<pair<int, int>> &res) const {
if (!t || r < tl || tr < l) {
return;
}
if (tl == tr) {
for (int &i : t->idxs) {
res.push_back({tl, i});
}
return;
}
int tm = (tl + tr) / 2;
iterate(t->l, tl, tm, l, r, res);
iterate(t->r, tm + 1, tr, l, r, res);
}
public:
ordered_set(int n) : tl(0), tr(n - 1), t(new node()) {}
~ordered_set() { delete t; }
void insert(int x, int idx) { insert(t, tl, tr, x, idx); }
int count_in(int l, int r) { return count_in(t, tl, tr, l, r); }
vector<pair<int, int>> iterate(int l, int r) const {
vector<pair<int, int>> res;
iterate(t, tl, tr, l, r, res);
return res;
}
ordered_set *merge(ordered_set *r) {
assert(tl == 0);
ordered_set *ans = new ordered_set(tr + 1);
for (auto &[elem, idx] : iterate(tl, tr)) {
ans->insert(elem, idx);
}
for (auto &[elem, idx] : r->iterate(r->tl, r->tr)) {
ans->insert(elem, idx);
}
return ans;
}
};
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<ordered_set *> seg(2 * buff_x.size());
for (int i = buff_x.size(); i < 2 * buff_x.size(); ++i) {
seg[i] = new ordered_set(buff_y.size());
}
for (int i = 0; i < n; ++i) {
seg[buff_x.size() + comp_x_lb(a[i].first)]->insert(comp_y_lb(a[i].second), i);
}
for (int i = buff_x.size() - 1; i >= 1; --i) {
seg[i] = seg[2 * i]->merge(seg[2 * i + 1]);
}
auto in_rect = [&](int64_t lx, int64_t rx, int64_t ly, int64_t ry) {
int 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 += seg[lx++]->count_in(ly, ry);
}
if (rx & 1) {
ans += seg[--rx]->count_in(ly, ry);
}
}
return ans;
};
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) {
for (auto &[val, idx] : seg[lx++]->iterate(ly, ry)) {
res.push_back(idx);
}
}
if (rx & 1) {
for (auto &[val, idx] : seg[--rx]->iterate(ly, ry)) {
res.push_back(idx);
}
}
}
return res;
};
int64_t dist = *ranges::partition_point(views::iota(int64_t(1), int64_t(4e9) + 1), [&](int dist) {
int ans = 0;
for (auto &[x, y] : a) {
ans += in_rect(x - dist, x + dist, y - dist, y + dist);
}
return (ans - n) / 2 < k;
});
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; i < dists.size() && j < k; i += 2, ++j) {
cout << dists[i] << '\n';
}
for (auto &i : seg) {
delete i;
}
}
