#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 5, inf = 2e9;
pair<int, int> p[maxn];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
for(int i = 1; i <= n; i++){
int x, y; cin >> x >> y;
p[i] = {x + y, x - y};
}
sort(p + 1, p + n + 1);
auto ok = [&](int mid){
multiset<int> ms;
int l = 1, cnt = 0;
for(int i = 1; i <= n; i++){
while(p[i].first - p[l].first > mid) ms.erase(ms.find(p[l++].second));
auto it = ms.lower_bound(p[i].second - mid);
for(;it != ms.end(); ++it){
if((*it) > p[i].second + mid) break;
cnt++;
if(cnt > k) return false;
}
ms.insert(p[i].second);
}
return true;
};
int l = 0, r = 4e9, ans;
while(l <= r){
int mid = (l + r) / 2;
if(ok(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
set<pair<int, int>>s;
vector<int>res;
int lp = 1;
for(int i = 1; i <= n; i++){
while(p[i].first - p[lp].first > ans){
s.erase(make_pair(p[lp].second, p[lp].first)); lp++;
}
auto it = s.lower_bound(make_pair(p[i].second - ans, -inf));
for(;it != s.end(); ++it){
auto [candy, candx] = (*it);
int dist = max(p[i].first - candx, abs(p[i].second - candy));
if(dist <= ans){
res.push_back(dist);
}else{
break;
}
}
s.insert(make_pair(p[i].second, p[i].first));
}
sort(res.begin(), res.end());
for(auto x: res) cout << x << "\n";
for(int i = 1; i <= k - res.size(); i++) cout << ans + 1 << "\n";
}
