#include <stdio.h>
#include <stdlib.h>
#define N 250000
#define M (250000 * 30)
#define assert_(x) if (!((x))) __builtin_trap()
int n, k,
ii[N], /* indices sorted by x */
ii2[N], /* indices sorted by y */
rt[1 + N], L[M], R[M], jj,
eo;
int x3[N], y3[N];
long long x[N], y[N],
x2[N], y2[N],
ee[N * 2];
long long A[M]; /* persistent segment tree */
int direction(long long x)
{
return x > 0 ? 1 : (x ? -1 : 0);
}
int cc(const void *i, const void *j)
{
return direction(*(long long*)i - *(long long*)j);
}
int ccx(const void *i, const void *j)
{
return direction(x[*(int*)i] - x[*(int*)j]);
}
int ccy(const void *i, const void *j)
{
return direction(y[*(int*)i] - y[*(int*)j]);
}
int lower_bound(long long *a, int n, long long x)
{
int lower, upper, mid;
lower = -1;
upper = n;
while (upper - lower > 1)
{
mid = lower + (upper - lower) / 2;
if (a[mid] >= x)
upper = mid;
else
lower = mid;
}
return upper;
}
int prev_upper_bound(long long *a, int n, int x)
{
int lower, upper, mid;
lower = -1;
upper = n;
while (upper - lower > 1)
{
mid = lower + (upper - lower) / 2;
if (a[mid] <= x)
lower = mid;
else
upper = mid;
}
return lower;
}
int persist_new(int lc, int rc, long long v)
{
int i;
i = ++jj;
A[i] = A[lc] + A[rc] + v;
L[i] = lc;
R[i] = rc;
return i;
}
int persist_add(int v, int l, int r, int p, int k)
{
if (l == r)
return persist_new(0, 0, A[v] + k);
if (p <= (l + r) / 2)
return persist_new(persist_add(L[v], l, (l + r) / 2, p, k), R[v], 0);
return persist_new(L[v], persist_add(R[v], (l + r) / 2 + 1, r, p, k), 0);
}
long long persist_sum(int v, int l, int r, int x, int y)
{
if (r < x || y < l)
return 0;
if (x <= l && r <= y)
return A[v];
return persist_sum(L[v], l, (l + r) / 2, x, y)
+ persist_sum(R[v], (l + r) / 2 + 1, r, x, y);
}
long long count(long long v)
{
long long z;
int i, p_left, p_right;
jj = 0;
rt[0] = 0;
for (i = 0; i < n; ++i)
rt[i + 1] = persist_add(rt[i], 0, n, y3[ii[i]], 1);
z = 0;
p_left = 0;
p_right = 0;
for (i = 0; i < n; ++i)
{
int y_1, y_2;
while (p_right < n && x[ii[p_right]] <= v + x[ii[i]])
++p_right;
while (p_left < i && x[ii[p_left]] + v < x[ii[i]])
++p_left;
y_1 = lower_bound(y2, n, y[ii[i]] - v);
y_2 = prev_upper_bound(y2, n, y[ii[i]] + v);
--z;
assert_(p_left <= i);
z += persist_sum(rt[p_right], 0, n, y_1, y_2) - persist_sum(rt[p_left], 0, n, y_1, y_2);
}
return z / 2;
}
void input()
{
int i, xx, yy;
scanf("%d%d", &n, &k);
for (i = 0; i < n; ++i)
{
scanf("%d%d", &xx, &yy);
x[i] = xx + yy;
y[i] = xx - yy;
x2[i] = x[i];
y2[i] = y[i];
}
}
void prepare()
{
int i;
qsort(x2, n, sizeof *x2, cc);
qsort(y2, n, sizeof *y2, cc);
for (i = 0; i < n; ++i)
{
ii[i] = i;
ii2[i] = i;
}
qsort(ii, n, sizeof *ii, ccx);
qsort(ii2, n, sizeof *ii2, ccy);
for (i = 0; i < n; ++i)
{
x3[i] = lower_bound(x2, n, x[i]);
y3[i] = lower_bound(y2, n, y[i]);
}
}
unsigned kth(int k)
{
unsigned lower, upper;
lower = 0;
upper = 4e9 + 1;
while (upper - lower > 1)
{
unsigned mid;
mid = lower + (upper - lower) / 2;
if (count(mid) >= k)
upper = mid;
else
lower = mid;
}
return upper;
}
long long max(long long a, long long b)
{
return a > b ? a : b;
}
long long distance(int i, int j)
{
return max(llabs(x[i] - x[j]), llabs(y[i] - y[j]));
}
void make_edge(int i, int j, long long threshold)
{
long long dd;
dd = distance(i, j);
if (eo >= k)
return;
if (persist_sum(rt[i], 0, n, j, j))
return;
if (dd > threshold)
return;
rt[i] = persist_add(rt[i], 0, n, j, 1);
ee[eo++] = distance(i, j);
}
void fetch_not_exceeding(long long d)
{
int i, j, k;
j = 0;
for (i = 0; i < n; ++i)
{
while (j < n && x[ii[j]] <= x[ii[i]] + d)
++j;
for (k = i + 1; k < j; ++k)
make_edge(ii[i], ii[k], d);
}
j = 0;
for (i = 0; i < n; ++i)
{
while (j < n && y[ii2[j]] <= y[ii2[i]] + d)
++j;
for (k = i + 1; k < j; ++k)
make_edge(ii2[i], ii2[k], d);
}
}
void answer()
{
unsigned last;
int i;
last = kth(k);
jj = 0;
for (i = 0; i < n; ++i)
rt[i] = 0;
fetch_not_exceeding(last - 1);
fetch_not_exceeding(last);
qsort(ee, eo, sizeof *ee, cc);
for (i = 0; i < k; ++i)
printf("%lld\n", ee[i]);
}
void debug()
{
int i;
return;
printf("x2[] : ");
for (i = 0; i < n; ++i) printf(" %lld", x2[i]);
puts("");
printf("y2[] : ");
for (i = 0; i < n; ++i) printf(" %lld", y2[i]);
puts("");
printf("x3[] : ");
for (i = 0; i < n; ++i) printf(" %d", x3[i]);
puts("");
printf("y3[] : ");
for (i = 0; i < n; ++i) printf(" %d", y3[i]);
puts("");
printf("ii[] : ");
for (i = 0; i < n; ++i) printf(" %d", ii[i]);
puts("");
printf("count(1) = %lld\n",count(1));
printf("count(10) = %lld\n",count(10));
}
int main()
{
input();
prepare();
debug();
answer();
return 0;
}
