#include <stdio.h>
#define N 250000
#define M 250000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long abs_(long long a) { return a > 0 ? a : -a; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long xx[N], yy[N]; int ii[N], n;
long long dd[M]; int hh[M], m;
long long *vv;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (vv[ii[j]] == vv[i_])
j++;
else if (vv[ii[j]] < vv[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int zz[N + 1], ll[N + 1], rr[N + 1], ii_[N + 1], _, u_, l_, r_;
int node(int i) {
zz[_] = rand_();
ll[_] = rr[_] = 0;
ii_[_] = i;
return _++;
}
void split(int u, int i) {
int c;
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
c = yy[ii_[u]] != yy[i] ? (yy[ii_[u]] < yy[i] ? -1 : 1) : ii_[u] - i;
if (c < 0) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (c > 0) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
void tr_add(int i) {
split(u_, i);
u_ = merge(merge(l_, node(i)), r_);
}
void tr_remove(int i) {
split(u_, i);
u_ = merge(l_, r_);
}
int tr_higher(long long y, int i) {
int u = u_, i_ = -1;
while (u)
if (yy[ii_[u]] < y || yy[ii_[u]] == y && ii_[u] <= i)
u = rr[u];
else
i_ = ii_[u], u = ll[u];
return i_;
}
int count(int m, long long d) {
int i, i_, j, j_, cnt;
cnt = 0, _ = 1, u_ = 0;
for (i = 0, j = 0; j < n; j++) {
j_ = ii[j];
while (xx[j_] - xx[i_ = ii[i]] > d)
tr_remove(i_), i++;
i_ = tr_higher(yy[j_] - d, -1);
while (i_ != -1 && yy[i_] - yy[j_] <= d) {
dd[cnt++] = max(abs_(xx[i_] - xx[j_]), abs_(yy[i_] - yy[j_]));
if (cnt == m)
return m;
i_ = tr_higher(yy[i_], i_);
}
tr_add(j_);
}
return cnt;
}
int main() {
int cnt, h, i;
long long lower, upper, d;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
xx[i] = x + y, yy[i] = x - y;
}
for (i = 0; i < n; i++)
ii[i] = i;
vv = xx, sort(ii, 0, n);
lower = 0, upper = INF;
while (upper - lower > 1) {
d = (lower + upper) / 2;
if (count(m, d) < m)
lower = d;
else
upper = d;
}
d = upper;
cnt = count(m, d - 1);
while (cnt < m)
dd[cnt++] = d;
for (h = 0; h < m; h++)
hh[h] = h;
vv = dd, sort(hh, 0, m);
for (h = 0; h < m; h++)
printf("%lld\n", dd[hh[h]]);
return 0;
}
