//I wrote this code 4 u <3
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<T>>;
struct WT {
vector<vector<ll>> t, pref;
vector<ll> srt;
int sz;
WT(vector<ll>& a) {
srt = a;
sort(srt.begin(), srt.end());
srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
sz = 1;
while (sz < (int) srt.size()) sz <<= 1;
t.resize(sz << 1);
pref.resize(sz << 1);
for (auto& x : a) x = lower_bound(srt.begin(), srt.end(), x) - srt.begin();
t[1] = a;
build(1, 0, srt.size());
}
void build(int x, int lx, int rx) {
if (lx + 1 == rx) return;
int m = (lx + rx) >> 1;
pref[x].resize(t[x].size() + 1);
for (int i = 0; i < (int) t[x].size(); ++i) {
bool le = (t[x][i] < m);
pref[x][i + 1] = pref[x][i] + le;
if (le) {
t[x << 1].push_back(t[x][i]);
} else {
t[x << 1 | 1].push_back(t[x][i]);
}
}
build(x << 1, lx, m);
build(x << 1 | 1, m, rx);
}
int le(int l, int r, int v, int x, int lx, int rx) {
if (lx >= v) return 0;
if (rx <= v) return r - l;
int m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r];
return le(lb, rb, v, x << 1, lx, m) + le(l - lb, r - rb, v, x << 1 | 1, m, rx);
}
int le(int l, int r, ll v) { // counting elements lower than v in [l, r)
v = lower_bound(srt.begin(), srt.end(), v) - srt.begin();
return le(l, r, v, 1, 0, srt.size());
}
};
const ll inf = 4e9;
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<ll, ll>> a(n);
for (auto& c : a) {
ll x, y;
cin >> x >> y;
c = {x + y, x - y};
}
sort(a.begin(), a.end());
vector<ll> y(n);
for (int i = 0; i < n; ++i) y[i] = a[i].second;
WT tt(y);
auto counting = [&](int i, ll m) {
ll rx = a[i].first + m, ly = a[i].second - m, ry = a[i].second + m;
rx = upper_bound(a.begin(), a.end(), pair{rx, inf}) - a.begin();
return tt.le(i, rx, ry + 1) - tt.le(i, rx, ly);
};
vector<ll> cnt(n, 1);
auto solve = [&](int i) {
ll lx = -1, rx = inf;
while (lx + 1 < rx) {
ll m = (lx + rx) >> 1;
if (counting(i, m) <= cnt[i]) {
lx = m;
} else {
rx = m;
}
}
return rx;
};
normal_queue<pair<ll, int>> pq;
for (int i = 0; i < n - 1; ++i) {
pq.emplace(solve(i), i);
}
while (k--) {
auto [d, j] = pq.top(); pq.pop();
cnt[j]++;
cout << d << '\n';
if (cnt[j] != n - j) pq.emplace(solve(j), j);
}
}
/*
*/
