#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;
int n, k, x[250000], y[250000];
ll ans;
int main() {
cin >> n >> k;
k = n + k * 2;
vector<int> cc;
for (int i = n; i--;) {
cin >> x[i] >> y[i];
tie(x[i], y[i]) = pint{x[i] + y[i], x[i] - y[i]};
cc.emplace_back(x[i]);
}
sort(all(cc));
cc.erase(unique(all(cc)), cc.end());
auto idx = [&] (ll x) {
if (x <= cc[0]) return 0;
if (x > cc.back()) return (int) cc.size();
return (int) (lower_bound(all(cc), x) - cc.begin());
};
for (int K = 32; K--;) {
ans += 1ll << K;
vector<array<ll, 3>> v;
for (int i = n; i--;) {
v.push_back({y[i] - ans, -1, i});
v.push_back({y[i], 0, i});
v.push_back({y[i] + ans, 1, i});
}
sort(all(v));
struct St {
int n;
vector<int> st;
St(int n) : n(n), st(n << 1) {}
void upd(int i, int v) {
for (i += n; i; i >>= 1) st[i] += v;
}
int operator()(int l, int r) {
int ret = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret += st[l++];
if (r & 1) ret += st[--r];
}
return ret;
}
} st{(int) cc.size()};
ll cnt = 0;
for (auto &[yi, a, i]: v) {
if (a) cnt += a * st.operator()(idx(x[i] - ans), idx(x[i] + ans + 1));
else st.upd(idx(x[i]), 1);
}
if (cnt > k) ans -= 1 << K;
}
struct St2 {
int n;
vector<vector<int>> st;
St2(int n) : n(n), st(n << 1) {}
void upd(int i, int j) {
for (i += n; i; i >>= 1) st[i].emplace_back(j);
}
void operator()(int l, int r, int j, vector<ll> &v) {
auto add = [&] (vector<int> &a) {
for (int i = a.size(); i-- and y[a[i]] >= y[j] - ans;) v.emplace_back(max(abs((ll) x[a[i]] - x[j]), abs((ll) y[a[i]] - y[j])));
};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) add(st[l++]);
if (r & 1) add(st[--r]);
}
}
} st{(int) cc.size()};
vector<array<ll, 3>> v;
for (int i = n; i--;) {
v.push_back({y[i], 0, i});
v.push_back({y[i] + ans, 1, i});
}
sort(all(v));
vector<ll> dists;
for (auto &[yi, a, i]: v) {
if (a) st(idx(x[i] - ans), idx(x[i] + ans + 1), i, dists);
else st.upd(idx(x[i]), i);
}
sort(all(dists));
while (dists.size() < k) dists.emplace_back(ans + 1);
for (int i = n; i < k; i += 2) cout << dists[i] << endl;
}
