#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#include <stdio.h>
#include <stdlib.h>
#define N (1 << 18)
#define M (1 << 24)
#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];
int x3[N], y3[N]; /* x2[x3[i]] = x[i] */
long long x[N], y[N]; /* inputs, transformed to (x+y, x-y) */
int x2[N], y2[N]; /* sorted x[] and y[] */
unsigned ee[N * 2]; /* answers */
int eo;
int A[M], L[M], R[M], jj; /* persistent segment tree */
int *tt[N * 2], to[N * 2]; /* merge sort tree */
int pool[M], alloc; /* for merge sort tree */
int *pool_alloc(int n);
long long max(long long a, long long b);
unsigned distance(int i, int j);
void input();
void prepare();
void answer();
int lower_bound(int *a, int n, long long x);
int prev_upper_bound(int *a, int n, long long x);
int persist_new(int lc, int rc, int v);
int persist_add(int v, int l, int r, int p, int k);
int persist_sum(int v, int l, int r, int x, int y);
void fetch_not_exceeding(unsigned dist);
void construct_merge_sort_tree();
unsigned kth(int k);
long long count(long long v);
int direction(long long x)
{
return x > 0 ? 1 : (x ? -1 : 0);
}
int cci(const void *i, const void *j)
{
return direction(*(int*)i * 1ll - *(int*)j);
}
int ccu(const void *i, const void *j)
{
return direction((long long)(*(unsigned*)i) - (long long)(*(unsigned*)j));
}
int ccx(const void *i, const void *j)
{
return direction((long long)x[*(int*)i] - (long long)x[*(int*)j]);
}
int ccy(const void *i, const void *j)
{
return direction((long long)y[*(int*)i] - (long long)y[*(int*)j]);
}
int main()
{
input();
prepare();
construct_merge_sort_tree();
answer();
return 0;
}
void input()
{
int i, xx, yy;
(void)scanf("%d%d", &n, &k);
for (i = 0; i < n; ++i)
{
(void)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, cci);
qsort(y2, n, sizeof *y2, cci);
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]);
}
}
void answer()
{
unsigned last;
int i;
last = kth(k);
fprintf(stderr, "kth(%d) = %u\n", k, last);
fetch_not_exceeding(last - 1);
fetch_not_exceeding(last);
qsort(ee, eo, sizeof *ee, ccu);
for (i = 0; i < k; ++i)
printf("%u\n", ee[i]);
}
int lower_bound(int *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(int *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)
lower = mid;
else
upper = mid;
}
return lower;
}
int persist_new(int lc, int rc, int 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);
}
int 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 max(long long a, long long b)
{
return a > b ? a : b;
}
unsigned distance(int i, int j)
{
return max(llabs(x[i] - x[j]), llabs(y[i] - y[j]));
}
unsigned kth(int k)
{
unsigned lower, upper, mid;
lower = 0;
upper = 4e9 + 1;
while (upper - lower > 1)
{
mid = lower + (upper - lower) / 2;
if (count(mid) >= k)
upper = mid;
else
lower = mid;
}
return upper;
}
void construct_merge_sort_tree()
{
int i, j;
for (i = 0; i < n; ++i)
for (j = x3[ii2[i]] + n; j; j /= 2)
++to[j];
for (i = 1; i < 2 * n; ++i)
{
tt[i] = pool_alloc(to[i]);
to[i] = 0;
}
for (i = 0; i < n; ++i)
for (j = x3[ii2[i]] + n; j; j /= 2)
tt[j][to[j]++] = ii2[i];
}
void make_edge(int i, int j)
{
if (i == j || eo >= k)
return;
ee[eo++] = distance(i, j);
}
int mode;
void fetch_in_node(int i, int v, long long dist)
{
int j, lower, upper, mid;
lower = -1, upper = to[v];
while (upper - lower > 1)
{
mid = lower + (upper - lower) / 2;
if (y[tt[v][mid]] >= (mode ? y[i] + 1: y[i] - dist))
upper = mid;
else
lower = mid;
}
j = upper;
while (eo < k && j < to[v] && y[tt[v][j]] <= y[i] + dist)
make_edge(i, tt[v][j++]);
}
void fetch_(int i, int l, int r, long long dist)
{
for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
{
if (l & 1)
fetch_in_node(i, l++, dist);
if (r & 1)
fetch_in_node(i, --r, dist);
}
}
void fetch_not_exceeding(unsigned dist)
{
int w, i;
for (i = 0; eo < k && i < n; ++i)
{
w = prev_upper_bound(x2, n, dist + x[i]);
mode = 0;
fetch_(i, x3[i] + 1, w, dist);
mode = 1;
fetch_(i, x3[i], x3[i], dist);
}
}
void prepare_count()
{
static int f = 0;
if (!f)
++f;
else
return;
int i;
if (!rt[1])
{
jj = 0;
rt[0] = 0;
for (i = 0; i < n; ++i)
rt[i + 1] = persist_add(rt[i], 0, n, y3[ii[i]], 1);
}
}
long long count(long long v)
{
long long z;
int i, p_left, p_right, y_1, y_2;
prepare_count();
z = 0;
p_left = 0;
p_right = 0;
for (i = 0; i < n; ++i)
{
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 += persist_sum(rt[p_right], 0, n, y_1, y_2) - persist_sum(rt[p_left], 0, n, y_1, y_2);
}
return (z - n) / 2;
}
int *pool_alloc(int n)
{
int *u;
u = pool + alloc;
alloc += n;
return u;
}
