#include <bits/stdc++.h>
using ll = long long;
const int N = 2.5e5 + 10;
const int MEM = 1e7;
int lc[MEM], rc[MEM], sm[MEM], tsz = 1;
int update(int k, int t, int l, int r) {
int u = tsz++;
if (t) {
lc[u] = lc[t], rc[u] = rc[t], sm[u] = sm[t];
}
++sm[u];
if (l != r) {
int m = (l + r) / 2;
if (k <= m) lc[u] = update(k, lc[u], l, m);
else rc[u] = update(k, rc[u], m + 1, r);
}
return u;
}
int get(int ql, int qr, int t, int l, int r) {
if (r < ql || qr < l || !t) return 0;
if (ql <= l && r <= qr) return sm[t];
int m = (l + r) / 2;
return get(ql, qr, lc[t], l, m) + get(ql, qr, rc[t], m + 1, r);
}
int n;
ll x[N], y[N];
std::pair<ll, ll> xy[N];
int tr[N];
int get(int k, int a, int b) {
return get(a, b, tr[k], 0, n - 1);
}
int get(int l, int r, int a, int b) {
return get(r + 1, a, b) - get(l, a, b);
}
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int k;
std::cin >> n >> k;
for (int i = 0; i < n; ++i) {
int x, y;
std::cin >> x >> y;
xy[i] = {x + y, x - y};
}
std::sort(xy, xy + n);
for (int i = 0; i < n; ++i) std::tie(x[i], y[i]) = xy[i];
std::sort(y, y + n);
tr[0] = 0;
for (int i = 0; i < n; ++i) {
int k = std::lower_bound(y, y + n, xy[i].second) - y;
tr[i + 1] = update(k, tr[i], 0, n - 1);
}
std::vector<int> ptr(n, 0);
std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int>>, std::greater<>> pq;
auto inc = [&](int i) -> void {
int k = ++ptr[i];
if (k > i) return;
ll L = 0, R = 4e9;
while (L != R) {
ll M = (L + R) / 2;
int l = std::lower_bound(x, x + n, xy[i].first - M) - x, r = i - 1;
int a = std::lower_bound(y, y + n, xy[i].second - M) - y, b = std::upper_bound(y, y + n, xy[i].second + M) - y - 1;
if (get(l, r, a, b) >= k) R = M;
else L = M + 1;
}
pq.emplace(L, i);
};
for (int i = 0; i < n; ++i) inc(i);
for (int i = 0; i < k; ++i) {
auto [val, id] = pq.top();
pq.pop();
std::cout << val << ' ';
inc(id);
}
}
