#include <algorithm>
#include <climits>
#include <compare>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
ll const INF = LLONG_MAX / 3;
struct point {
ll x, y;
auto operator <=>(point const& rhs) const = default;
point swapped() const {
return { y, x };
}
ll dist(point const& rhs) const {
return max(abs(x - rhs.x), abs(y - rhs.y));
}
};
vector<ll> attempt(vector<point> const& cities, ll const dist, ll const k) {
set<point> possible;
ll i = 0;
vector<ll> ret;
for (ll j = 0; j < cities.size(); j++) {
while (cities[j].x - cities[i].x > dist) {
possible.erase(cities[i].swapped());
i++;
}
auto const lo = possible.lower_bound({ cities[j].y - dist, -INF });
auto const hi = possible.lower_bound({ cities[j].y + dist, INF });
for (auto it = lo; it != hi; ++it) {
ret.push_back(cities[j].swapped().dist(*it));
if (ret.size() == k)
return ret;
}
possible.insert(cities[j].swapped());
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, k;
cin >> n >> k;
vector<point> cities(n);
for (point& p : cities) {
ll x, y;
cin >> x >> y;
p = { x + y, x - y };
}
sort(cities.begin(), cities.end());
ll lo = 0;
ll hi = 4'000'000'010;
while (lo + 1 != hi) {
ll const mid = (lo + hi) / 2;
auto const result = attempt(cities, mid, k);
if (result.size() >= k)
hi = mid;
else
lo = mid;
}
auto ans = attempt(cities, lo, k);
sort(ans.begin(), ans.end());
ans.resize(k, lo + 1);
for (ll const& x : ans)
cout << x << "\n";
}
