#include <stdio.h>
#define N 250000
#define M (250000 * 30)
int n, k,
x[N], y[N], /* inputs */
x2[N], y2[N], /* x[] and y[] seperatedly sorted */
x3[N], y3[N], /* x2[x3[i]] = x[i] */
ii[N], /* indices sorted by x */
ii2[N], /* indices sorted by y */
rt[N], L[M], R[M], jj,
ee[N * 2], eo;
long long A[M]; /* persistent segment tree */
void csort(int *a, int n, int offset)
{
#define B 45000
int i;
static int count[B],
pass_1[N];
for (i = 0; i < B; ++i)
count[i] = 0;
for (i = 0; i < n; ++i)
{
a[i] += offset;
++count[a[i] % B];
}
for (i = B - 2; i >= 0; --i)
count[i] += count[i + 1];
for (i = 0; i < n; ++i)
pass_1[--count[a[i] % B]] = a[i];
for (i = 0; i < B; ++i)
count[i] = 0;
for (i = 0; i < n; ++i)
++count[pass_1[i] / B];
for (i = 1; i < B; ++i)
count[i] += count[i - 1];
for (i = 0; i < n; ++i)
a[--count[pass_1[i] / B]] = pass_1[i] - offset;
#undef B
}
int lower_bound(int *a, int n, long long x)
{
int lower, upper;
lower = -1;
upper = n;
while (upper - lower > 1)
{
int mid;
mid = lower + (upper - lower) / 2;
if (a[mid] >= x)
upper = mid;
else
lower = mid;
}
return upper;
}
int prev_upper_bound(int *a, int n, int x)
{
int lower, upper;
lower = -1;
upper = n;
while (upper - lower > 1)
{
int mid;
mid = lower + (upper - lower) / 2;
if (a[mid] <= x)
lower = mid;
else
upper = mid;
}
return lower;
}
int persist_new0(int val)
{
int i;
i = ++jj;
A[i] = val;
L[i] = R[i] = 0;
return i;
}
int persist_new1(int lc, int rc)
{
int i;
i = ++jj;
A[i] = A[lc] + A[rc];
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_new0(A[v] + k);
if (p <= (l + r) / 2)
return persist_new1(persist_add(L[v], l, (l + r) / 2, p, k), R[v]);
return persist_new1(L[v], persist_add(R[v], (l + r) / 2 + 1, r, p, k));
}
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 + 1 < n && x[ii[p_right + 1]] <= 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;
z += persist_sum(rt[p_right + 1], 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()
{
static int freq[N], ptr[N];
int i, run;
csort(x2, n, 1e9);
csort(y2, n, 1e9);
for (i = 0; i < n; ++i)
{
x3[i] = lower_bound(x2, n, x[i]);
y3[i] = lower_bound(y2, n, y[i]);
++freq[x3[i]];
}
run = 0;
for (i = 0; i < n; ++i)
{
ptr[i] = run;
run += freq[i];
}
for (i = 0; i < n; ++i)
ii[ptr[x3[i]]++] = i;
for (i = 0; i < n; ++i)
{
ptr[i] = 0;
freq[i] = 0;
}
for (i = 0; i < n; ++i)
++freq[y3[i]];
run = 0;
for (i = 0; i < n; ++i)
{
ptr[i] = run;
run += freq[i];
}
}
unsigned kth()
{
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 abs_(long long x)
{
return x < 0 ? -x : x;
}
long long max(long long a, long long b)
{
return a > b ? a : b;
}
long long distance(int i, int j)
{
return max(abs_(x[i] * 1ll - x[j]), abs_(y[i] * 1ll - y[j]));
}
void make_edge(int i, int j, long long threshold)
{
long long 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);
if (ee[eo - 1] > 2e9)
__builtin_trap();
}
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(i, k, d);
}
j = 0;
for (i = 0; i < n; ++i)
{
while (j < n && y[ii[j]] <= y[ii[i]] + d)
++j;
for (k = i + 1; k < j; ++k)
make_edge(i, k, d);
}
}
void answer()
{
unsigned last;
int i;
last = kth();
jj = 0;
for (i = 0; i < n; ++i)
rt[i] = 0;
if (last == 0)
__builtin_trap();
fetch_not_exceeding(last - 1);
fetch_not_exceeding(last);
csort(ee, eo, 0);
for (i = 0; i < k; ++i)
printf("%d\n", ee[i]);
}
void debug()
{
int i;
return;
printf("x2[] : ");
for (i = 0; i < n; ++i) printf(" %d", x2[i]);
puts("");
printf("y2[] : ");
for (i = 0; i < n; ++i) printf(" %d", 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;
}
