#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
const int N = 2.5e5 + 5;
int n, k;
pii a[N];
vector<int> compressed;
int bit[N];
int b[N];
pii p[N];
void update(int id, int val) {
for (int i = id; i <= compressed.size(); i += (i & -i)) bit[i] += val;
}
int get(int id) {
int res = 0;
for (int i = id; i >= 1; i -= (i & -i)) res += bit[i];
return res;
}
bool check(ll mid) {
for (int i = 1; i <= compressed.size(); i++) {
bit[i] = 0;
}
ll res = 0;
int j = 1;
for (int i = 1; i <= n; i++) {
while(a[i].F - a[j].F > mid) {
update(b[j], -1);
j++;
}
int right = upper_bound(compressed.begin(), compressed.end(), a[i].S + mid) - compressed.begin() - 1;
int left = lower_bound(compressed.begin(), compressed.end(), a[i].S - mid) - compressed.begin() - 1;
res += get(right) - get(left);
update(b[i], 1);
}
// cout << res;
return res >= k;
}
signed main(){
ios_base::sync_with_stdio(false) ;
cin.tie(0) ; cout.tie(0) ;
cin >> n >> k;
compressed.pb(-2e9);
for (int i = 1; i <= n; i++) {
cin >> p[i].F >> p[i].S;
a[i].F = p[i].F + p[i].S;
a[i].S = p[i].F - p[i].S;
compressed.pb(a[i].S);
}
sort(a + 1, a + 1 + n);
sort(compressed.begin(), compressed.end());
compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());
for (int i = 1; i <= n; i++) {
b[i] = lower_bound(compressed.begin(), compressed.end(), a[i].S) - compressed.begin();
}
// for (int i = 1; i <= n; i++) {
// cout << a[i].F << " " << a[i].S << " " << b[i] << endl;
// }
// check(1);
ll l = 1;
ll ans = 1e15;
ll r = 1e15;
while(l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
ans = min(ans, mid);
}
else {
l = mid + 1;
}
}
for (int i = 1; i <= compressed.size(); i++) {
bit[i] = 0;
}
int j = 1;
multiset<pii> st;
vector<ll> res;
res.pb(ans);
if (ans != 1) {
for (int i = 1; i <= n; i++) {
while(j < i && a[i].F - a[j].F >= ans) {
// update(b[j], -1);
st.erase(st.find({a[j].S, j}));
j++;
}
auto rig = st.lower_bound({a[i].S + ans, 0});
auto lef = st.upper_bound({a[i].S - ans, n + 1});
while(lef != st.end() && lef != rig) {
int id = (*lef).S;
if (max(a[i].F - a[id].F, abs(a[i].S - a[id].S)) >= ans) break;
res.pb(max(a[i].F - a[id].F, abs(a[i].S - a[id].S)));
lef++;
}
st.insert({a[i].S, i});
}
}
sort(res.begin(), res.end());
while(res.size() < k) res.pb(ans);
for (auto x : res) cout << x << '\n';
}
