#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define rrep(i, n) for (int i=1; i<=(n); ++i)
#define all(v) ((v).begin()), ((v).end())
#define x first
#define y second
using namespace std; using ll=long long; using pll=pair<ll,ll>;
const int maxn = 250'000 + 10;
int n, k;
pll p[maxn];
int xv[maxn], xvn;
int yv[maxn], yvn;
int xi[maxn], yi[maxn];
void In() {
cin.tie(0)->sync_with_stdio(0); cin >> n >> k; rep(i, n) cin >> p[i].x >> p[i].y;
rep(i, n) { auto [x, y] = p[i]; p[i] = {x+y, x-y}; }
sort(p, p+n);
}
void Cc() {
rep(i, n) xv[i] = p[i].x; sort(xv, xv+n); xvn = unique(xv, xv+n) - xv; rep(i, n) xi[i] = lower_bound(xv, xv+xvn, p[i].x) - xv;
rep(i, n) yv[i] = p[i].y; sort(yv, yv+n); yvn = unique(yv, yv+n) - yv; rep(i, n) yi[i] = lower_bound(yv, yv+yvn, p[i].y) - yv;
}
const int M = 262144;
struct Pst {
struct {
int pl, pr, val;
} node[2*M + maxn * 19];
int nn;
int init(int l=0, int r=xvn-1) {
int me = ++nn;
if (l != r) {
int mid = (l+r)/2;
node[me].pl = init(l, mid);
node[me].pr = init(mid+1, r);
}
return me;
}
int upd(int orig, int up, int l=0, int r=xvn-1) {
if (r < up || up < l) return orig;
int me = ++nn;
if (l == r) { node[me].val = node[orig].val + 1; return me; }
int mid = (l+r)/2;
node[me] = node[orig];
node[me].val++;
if (up <= mid) node[me].pl = upd(node[orig].pl, up, l, mid);
else node[me].pr = upd(node[orig].pr, up, mid+1, r);
return me;
}
int rsum(int nd, int ql, int qr, int l=0, int r=xvn-1) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return node[nd].val;
int mid = (l+r)/2;
return rsum(node[nd].pl, ql, qr, l, mid) +
rsum(node[nd].pr, ql, qr, mid+1, r);
}
} pst;
int roots[maxn];
vector<int> t[M<<1];
bool ycomp(const int& a, const int& b) { return p[a].y < p[b].y; }
void Bt() {
// pst
{
roots[0] = pst.init();
int cr = roots[0];
rep(i, n) {
cr = pst.upd(cr, yi[i]);
roots[1+xi[i]] = cr;
}
}
}
int Crect(ll l, ll r, ll d, ll u) {
l = lower_bound(xv, xv+xvn, l) - xv; r = lower_bound(xv, xv+xvn, r+1) - xv;
d = lower_bound(yv, yv+yvn, d) - yv; u = lower_bound(yv, yv+yvn, u+1) - yv - 1;
if (l>r || r<0 || d>u || u<0) return 0;
int ret = pst.rsum(roots[r], d, u);
if (l > 0) ret -= pst.rsum(roots[l], d, u);
return ret;
}
ll Count(ll rad) {
ll ret = 0;
rep(i, n) ret += Crect(p[i].x-rad, p[i].x+rad, p[i].y-rad, p[i].y+rad);
return ret;
}
ll ans[maxn], an;
void Add(int i, int j) {
ans[an++] = max(abs(p[i].x-p[j].x), abs(p[i].y-p[j].y));
}
void Enumerate(ll rad) {
rep(i, n) {
ll l = p[i].x-rad, r = p[i].x+rad, d = p[i].y-rad, u = p[i].y+rad;
l = lower_bound(xv, xv+xvn, l) - xv; r = lower_bound(xv, xv+xvn, r+1) - xv - 1;
d = lower_bound(yv, yv+yvn, d) - yv; u = lower_bound(yv, yv+yvn, u) - yv - 1;
}
}
int main()
{
In(); Cc(); Bt();
ll l = 0, r = ll(1e9) * 5;
while (l+1 < r) {
ll mid = (l+r)/2;
ll tmp = Count(mid);
tmp -= n; tmp /= 2;
if (tmp >= k) r = mid;
else l = mid;
}
Enumerate(l);
sort(ans, ans+an);
while (an < k) ans[an++] = r;
rep(i, k) cout << ans[i] << '\n';
return 0;
}
