#include <bits/stdc++.h>
using ll = long long;
const int N = 2.5e5;
std::vector<ll> fenw[N];
int n;
ll x[N], y[N];
std::pair<ll, ll> xy[N];
void add(int i, ll y) {
for (; i < n; i |= i + 1) fenw[i].push_back(y);
}
void build() {
for (int i = 0; i < n; ++i) {
std::sort(fenw[i].begin(), fenw[i].end());
}
}
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 k, ll a, ll b) {
int ret = 0;
for (; k >= 0; k &= k + 1, --k) ret += count(fenw[k], a, b);
return ret;
}
int get(int l, int r, ll a, ll b) {
return get(r, a, b) - get(l - 1, 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];
add(i, y[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);
}
}
