#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl
#else
#define bug(x)
#define cerr if (0) cerr
#endif
#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;
const int MAXN = 25e4;
int N, K;
i64 X[MAXN], Y[MAXN], x[MAXN], y[MAXN];
vector<i64> vx, vy;
vi at_x[MAXN];
// int tr[MAXN + 1];
/*
const int MAXS = MAXN * 20;
int lc[MAXS], rc[MAXS], sum[MAXS];
int tt;
void inc(int &k, int l, int r, int i) {
++tt;
lc[tt] = lc[k], rc[tt] = rc[k], sum[tt] = sum[k] + 1;
k = tt;
if (l < r) {
int m = (l + r) / 2;
i <= m ? inc(lc[k], l, m, i) : inc(rc[k], m + 1, r, i);
}
}
int qry(int k, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return sum[k];
int m = (l + r) / 2, x = 0;
if (ql <= m && lc[k]) x += qry(lc[k], l, m, ql, qr);
if (qr > m && rc[k]) x += qry(rc[k], m + 1, r, ql, qr);
return x;
}
*/
int get_count(i64 c) {
int num = 0;
vector<tuple<i64, int, int>> events;
for (int i = 0; i < N; i++) {
events.push_back({X[i] - c, 0, i});
events.push_back({X[i], 1, i});
events.push_back({X[i] + c, 2, i});
}
sort(all(events));
ordered_set<pair<i64, int>> os;
for (auto [x, t, i] : events)
if (t == 0) os.insert({Y[i], i});
else if (t == 2) os.erase({Y[i], i});
else {
num += os.order_of_key({Y[i] + c, MAXN}) - os.order_of_key({Y[i] - c, 0}) - 1;
if (num > K * 2) return K + 1;
}
// assert(num % 2 == 0);
return num / 2;
}
vector<i64> ans;
set<i64> open;
vi add[MAXN], del[MAXN];
set<pair<i64, int>> active;
void add_ans(i64 x) {
if (open.count(x)) open.erase(x);
else open.insert(x), ans.push_back(x);
}
i64 dist(int i, int j) {
return max(abs(i64(X[i]) - X[j]), abs(i64(Y[i]) - Y[j]));
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
tie(X[i], Y[i]) = pi(X[i] - Y[i], X[i] + Y[i]);
}
vx = vector(X, X + N), vy = vector(Y, Y + N);
sort(all(vx)), vx.erase(unique(all(vx)), end(vx));
sort(all(vy)), vy.erase(unique(all(vy)), end(vy));
for (int i = 0; i < N; i++) {
x[i] = lower_bound(all(vx), X[i]) - begin(vx);
y[i] = lower_bound(all(vy), Y[i]) - begin(vy);
at_x[x[i]].push_back(i);
}
/*
for (int i = 0; i < sz(vx); i++) {
tr[i + 1] = tr[i];
for (int j : at_x[i]) inc(tr[i + 1], 0, sz(vy) - 1, y[j]);
}
*/
i64 low = 0, hi = 4e9;
while (low < hi) {
i64 m = (low + hi) / 2 + 1;
get_count(m) <= K ? low = m : hi = m - 1;
}
i64 c = low;
for (int i = 0; i < N; i++) {
int d = lower_bound(all(vx), X[i] - c) - begin(vx);
int u = upper_bound(all(vx), X[i] + c) - begin(vx) - 1;
add[d].push_back(i);
del[u].push_back(i);
}
for (int i = 0; i < sz(vx); i++) {
for (int j : add[i]) active.insert({Y[j], j});
for (int j : at_x[i])
for (auto it = active.lower_bound({Y[j] - c, -1}); it != end(active) && it->first <= Y[j] + c; ++it)
if (j != it->second) add_ans(dist(j, it->second));
for (int j : del[i]) active.erase({Y[j], j});
}
// for (auto x : ans) bug(x);
// assert(get_count(c) == sz(ans));
sort(all(ans));
while (sz(ans) < K) ans.push_back(c + 1);
for (auto x : ans) cout << x << '\n';
}
