#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000009ll
#define ll long long
int n, k;
vector<ll> ans;
set<pair<ll, ll>> st;
map<ll, vector<ll>> mp;
queue<pair<ll, ll>> active;
bool check(ll mid){
ans.clear();
st.clear();
active = queue<pair<ll, ll>>();
for(auto &i : mp){
vector<ll> &v = i.second;
ll x = i.first;
while(!active.empty() && active.front().second < x-mid) st.erase(active.front()), active.pop();
for(auto &y : v){
auto it = st.lower_bound({y-mid, -INF});
while(it != st.end() && (*it).first <= y+mid){
ans.push_back(max(abs((*it).first-y),abs(x-(*it).second)));
if((int)ans.size() > k) return 0;
it = next(it);
}
st.insert({y, x});
active.push({y, x});
}
}
return 1;
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 0; i<n; i++){
ll a, b; cin >> a >> b;
mp[a+b].push_back(a-b);
}
for(auto &x : mp) sort(x.second.begin(), x.second.end());
ll lo = 1, hi = 4000000009;
while(lo < hi){
ll mid = lo+(hi-lo+1)/2;
if(check(mid)) lo = mid;
else hi = mid-1;
}
check(lo);
sort(ans.begin(), ans.end());
for(int i = 0; i<k; i++){
if(i < (int)ans.size()) cout << ans[i] << endl;
else cout << lo+1 << endl;
}
}
