#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }
const int N = 3e5 + 7;
int n, k;
pair<ll, ll> x[N];
ll get(ll d) {
ll cnt = 0;
set<pair<ll, int>> s;
int ptr1 = 1, ptr2 = 1;
for (int i = 1; i <= n; ++i) {
while (ptr1 <= n && x[ptr1].F < x[i].F - d) {
s.erase({x[ptr1].S, ptr1});
++ptr1;
}
while (ptr2 <= n && x[ptr2].F <= x[i].F + d) {
s.insert({x[ptr2].S, ptr2});
++ptr2;
}
auto it = s.lower_bound({x[i].S - d, 0});
while (it != s.end()) {
if (it->F > x[i].S + d) break;
++cnt;
if (cnt >= 2 * k + n) return k;
it = next(it);
}
}
return (cnt - n) / 2;
}
ll dist(int i, int j) {
return max(abs(x[i].F - x[j].F), abs(x[i].S - x[j].S));
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> x[i].F >> x[i].S;
for (int i = 1; i <= n; ++i) x[i] = {x[i].F + x[i].S, x[i].F - x[i].S};
sort(x + 1, x + n + 1);
ll l = 0, r = 1e10, sol = 0;
while (l <= r) {
ll m = (l + r) / 2;
if (get(m) >= k) {
sol = m;
r = m - 1;
} else {
l = m + 1;
}
}
vector<ll> v;
ll d = sol - 1;
set<pair<ll, int>> s;
int ptr1 = 1, ptr2 = 1;
for (int i = 1; i <= n; ++i) {
while (ptr1 <= n && x[ptr1].F < x[i].F - d) {
s.erase({x[ptr1].S, ptr1});
++ptr1;
}
while (ptr2 <= n && x[ptr2].F <= x[i].F + d) {
s.insert({x[ptr2].S, ptr2});
++ptr2;
}
auto it = s.lower_bound({x[i].S - d, 0});
while (it != s.end()) {
if (it->F > x[i].S + d) break;
if (it->S < i) v.push_back(dist(i, it->S));
it = next(it);
}
}
while (v.size() < k) v.push_back(sol);
sort(v.begin(), v.end());
for (auto i : v) cout << i << "\n";
}
