#include <bits/stdc++.h>
#include <bits/extc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<ll, ll>;
using oset = tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
int n, k;
vector<pii> v;
oset s;
void add(int t) {
s.insert({v[t].S, t});
}
void rm(int t) {
s.erase({v[t].S, t});
}
ll cnt(ll y, ll dist) {
return s.order_of_key({y + dist, INT_MAX}) - s.order_of_key({y - dist, INT_MIN});
}
void load() {
cin >> n >> k;
v.resize(n);
for (auto &[a, b] : v) {
ll ta, tb;
cin >> ta >> tb;
a = ta - tb;
b = ta + tb;
}
sort(all(v));
}
ll solve(ll dist) {
s.clear();
int prev = 0;
ll ret = 0;
for (int i = 0; i < n; ++i) {
while (prev < n && v[prev].F < v[i].F - dist) {
rm(prev++);
}
ret += cnt(v[i].S, dist);
if (ret >= k) return ret;
add(i);
}
return ret;
}
vector<ll> ans;
void construct(ll dist) {
set<pair<ll, int>> s;
int prev = 0;
for (int i = 0; i < n; ++i) {
while (prev < n && v[prev].F < v[i].F - dist) {
s.erase({v[prev].S, prev});
prev++;
}
for (auto it = s.lower_bound({v[i].S - dist, INT_MIN}); it != s.upper_bound({v[i].S + dist, INT_MAX}); ++it) {
ans.push_back(max(abs(v[i].F - v[it->S].F), abs(v[i].S - v[it->S].S)));
}
s.insert({v[i].S, i});
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
load();
ll lo = 1, hi = 4ll * 1e9 + 100;
while (lo < hi) {
ll mid = (lo + hi) / 2;
if (solve(mid) < k) {
lo = mid + 1;
} else hi = mid;
}
construct(lo - 1);
sort(all(ans));
ans.resize(k, lo);
for (auto a : ans) cout << a << '\n';
return 0;
}
