#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<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) {
pair<int, int> p2 = {ry, n}, p1 = {ly, -1};
vector<int> res;
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);
}
return res;
};
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 &idx : iterate(lx++, ly, ry)) {
res.push_back(idx);
}
}
if (rx & 1) {
for (auto &idx : iterate(--rx, 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;
}) - 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';
}
}
