#include <bits/stdc++.h>
using ll = long long;
const int N = 2.5e5;
std::vector<ll> tr[2 * N];
int n;
ll x[N], y[N];
std::pair<ll, ll> xy[N];
void build() {
for (int i = 0; i < n; ++i) {
tr[i + n] = {y[i]};
}
for (int i = n - 1; i > 0; --i) {
std::merge(tr[i << 1].begin(), tr[i << 1].end(), tr[i << 1 | 1].begin(), tr[i << 1 | 1].end(), std::back_inserter(tr[i]));
}
}
int count(std::vector<ll>& v, ll a, ll b) {
return std::upper_bound(v.begin(), v.end(), b) - std::lower_bound(v.begin(), v.end(), a);
}
int get(int l, int r, ll a, ll b) {
int ret = 0;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) ret += count(tr[l++], a, b);
if (~r & 1) ret += count(tr[r--], a, b);
}
return ret;
}
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];
build();
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, x[i] - M) - x, r = i - 1;
if (get(l, r, y[i] - M, y[i] + M) >= 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);
}
}
