#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 1e10;
struct pt {
int x, y, lcnt, rcnt, cur, id;
bool operator < (const pt &b) const {
return x + y < b.x + b.y;
}
};
struct thing {
int id, plus, l, r, delta;
bool operator < (const thing &b) const {
return plus < b.plus;
}
};
int n, k;
int fen[maxn];
vector<int> sub;
int dcl(int x) {return lower_bound(sub.begin(), sub.end(), x) - sub.begin();}
int dcr(int x) {return upper_bound(sub.begin(), sub.end(), x) - sub.begin() - 1;}
void update(int id, int len) {
while (id <= len) {
fen[id]++;
id += (id & -id);
}
}
int sum(int id) {
int val = 0;
while (id >= 1) {
val += fen[id];
id -= (id & -id);
}
return val;
}
void cunt(vector<pt> &vec, int dist, int sgn) {
int sz = vec.size();
sub = {-INF};
for (auto &[x, y, lcnt, rcnt, cur, id]:vec) sub.push_back(x - y);
sort(sub.begin(), sub.end()); sub.erase(unique(sub.begin(), sub.end()), sub.end());
int len = sub.size();
for (int i=0;i<=len;i++) fen[i] = 0;
vector<thing> qry;
for (int i=0;i<sz;i++) {
auto [x, y, lcnt, rcnt, cur, id] = vec[i];
qry.push_back({i, x + y - dist - 1, dcl(x - y - dist), dcr(x - y + dist), -1});
qry.push_back({i, x + y + dist, dcl(x - y - dist), dcr(x - y + dist), 1});
}
sort(qry.begin(), qry.end());
int pter = 0;
for (int i=0;i<sz;i++) {
// cout << i << " " << pter << endl;
auto [x, y, lcnt, rcnt, cur, id] = vec[i];
while (pter < sz*2 && qry[pter].plus < x + y) {
vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
pter++;
}
update(dcl(x - y), len);
}
while (pter < sz*2) {
vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
pter++;
}
}
vector<pair<int,int>> cnt[maxn];
void solve(int l, int r, vector<pt> &vec) {
if (l==r) return;
// if (l==1 && r==1) for (auto [x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << lcnt << " " << rcnt << endl;
// if (l==1 && r==1) exit(0);
int mid = (l+r)/2;
cunt(vec, mid, 1);
cunt(vec, l-1, -1);
vector<pt> L, R;
int total = 0;
// if (mid == 4) cout << vec.size() << " " << l << " " << r << endl;
// cout << l << " " << mid << " " << r << " " << vec.size() << endl;
for (auto &[x, y, lcnt, rcnt, cur, id]:vec) {
cur += lcnt;
cnt[id].push_back({mid, cur});
// if (id == 0) cout << "test " << l << " " << mid << " " << r << " " << cur << endl;
total += cur;
if (cur != lcnt) L.push_back({x, y, lcnt, cur, 0, id});
if (cur != rcnt) R.push_back({x, y, cur, rcnt, 0, id});
}
// cout << "L\n";
// for (auto [x, y, lcnt, rcnt, cur]:L) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
// cout << "R\n";
// for (auto [x, y, lcnt, rcnt, cur]:R) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
if (L.size()) solve(l, mid, L);
if (R.size() && total < 2*k) solve(mid+1, r, R);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
vector<pt> vec(n);
for (auto &[x, y, lcnt, rcnt, cur, id]:vec) cin >> x >> y, lcnt = 0, rcnt = n-1;
sort(vec.begin(), vec.end());
for (int i=0;i<n;i++) vec[i].id = i;
// for (auto &[x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << cur << endl;
solve(1, INF, vec);
map<int,int> mp;
for (int i=0;i<n;i++) {
sort(cnt[i].begin(), cnt[i].end());
// cout << "test " << vec[i].x << " " << vec[i].y << endl;
for (int j=0;j<cnt[i].size();j++) {
bool kill = false;
if (cnt[i][j].second == n-1) kill = true;
int freq = cnt[i][j].second;
if (j>0) freq -= cnt[i][j-1].second;
mp[cnt[i][j].first] += freq;
// cout << cnt[i][j].first << " " << freq << endl;
if (kill) break;
}
// cout << "test " << vec[i].x << " " << vec[i].y << endl;
// for (auto [dist, freq]:cnt[i]) if (dist<=12) cout << dist << " " << freq << endl;
}
int pos = 0;
for (auto [dist, freq]:mp) {
freq /= 2;
for (int i=0;i<freq;i++) {
pos++;
cout << dist << '\n';
if (pos == k) break;
}
if (pos == k) break;
}
}
