#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
template <class T> class Fenwick {
public:
int lim;
vector<T> bit;
Fenwick(int n) : lim(n + 1), bit(lim) {}
void upd(int pos, T val) {
for (pos++; pos < lim; pos += pos & -pos)
bit[pos] += val;
}
T sum(int r) { // < r
T ret = 0;
for (; r; r -= r & -r)
ret += bit[r];
return ret;
}
T sum(int l, int r) { // [l, r)
return sum(r) - sum(l);
}
};
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
K *= 2;
vector<pair<int, int>> points(N);
for (auto &[x, y] : points) {
cin >> x >> y;
tie(x, y) = make_pair(x - y, x + y);
}
vector<int> valY;
for (auto [x, y] : points)
valY.push_back(y);
sort(valY.begin(), valY.end());
valY.resize(unique(valY.begin(), valY.end()) - valY.begin());
int nbY = valY.size();
auto getId = [&](int y) {
return lower_bound(valY.begin(), valY.end(), y) - valY.begin();
};
sort(points.begin(), points.end());
auto countSmaller = [&](int L) { // cb avec dis <= L?
int sol = 0;
Fenwick<int> fen(nbY);
int l = 0, r = 0;
for (auto [x, y] : points) {
while (r < N and points[r].first <= x + L)
fen.upd(getId(points[r++].second), 1);
while (l < r and points[l].first < x - L) {
fen.upd(getId(points[l++].second), -1);
}
assert(l < r);
int fstGood = lower_bound(valY.begin(), valY.end(), y - L) - valY.begin();
int fstBad = upper_bound(valY.begin(), valY.end(), y + L) - valY.begin();
sol += fen.sum(fstGood, fstBad) - 1;
}
return sol;
};
int lo = 0, up = 1e18;
while (lo < up) {
int mid = (lo + up + 1) / 2;
if (countSmaller(mid) <= K)
lo = mid;
else
up = mid - 1;
}
int L = lo;
vector<int> costs;
int add = K - countSmaller(L);
for (int i = 0; i < add; ++i)
costs.push_back(L + 1);
int l = 0, r = 0;
set<pair<int, int>> possible;
for (int i = 0; i < N; ++i) {
auto [x, y] = points[i];
while (r < N and points[r].first <= x + L) {
possible.emplace(points[r].second, r);
++r;
}
while (l < r and points[l].first < x - L) {
possible.erase({points[l].second, l});
++l;
}
for (auto it = possible.lower_bound(pair(y - L, 0));
it != possible.end() and it->first <= y + L; ++it) {
auto [x2, y2] = points[it->second];
if (i != it->second)
costs.push_back(max(abs(x2 - x), abs(y2 - y)));
}
}
sort(costs.begin(), costs.end());
for (int i = 0; i < K; i += 2)
cout << costs[i] << '\n';
}
