#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, k;
vector<pair<ll, ll>> v;
vector<ll> ans;
bool check(ll mid) {
ans.clear();
set<pair<ll, ll>> st;
st.insert({v[0].second, 0});
int l = 0;
for(int i = 1; i < n; i++) {
while(v[i].first - v[l].first > mid) {
st.erase({v[l].second, l});
l++;
}
auto it = st.lower_bound({v[i].second - mid, -1});
while(it != st.end() && abs(v[i].second - it->first) <= mid) {
ans.push_back({max(abs(v[i].first - v[it->second].first), abs(v[i].second - v[it->second].second))});
it++;
}
if((int)ans.size() > k) return 0;
st.insert({v[i].second, i});
}
return 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
v.resize(n);
for(int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
v[i] = {x + y, x - y};
}
sort(v.begin(), v.end());
ll l = 0, r = (ll)1e10;
while(r - l > 1) {
ll mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
check(l);
// cout << l << ' ' << r << '\n';
sort(ans.begin(), ans.end());
while((int)ans.size() < k) ans.push_back(r);
for(ll c : ans)
cout << c << '\n';
}
