#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxA = 1e10;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
pair<ll, ll> p[n];
for(int x=0;x<n;x++){
cin >> p[x].first >> p[x].second;
p[x] = {p[x].first+p[x].second+maxA, p[x].first-p[x].second+maxA};
}
vector<pair<ll, ll>> vX, vY;
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
for(int x=0;x<n;x++){
vX.push_back({p[x].first, x});
vY.push_back({p[x].second, x});
}
sort(vX.begin(), vX.end());
sort(vY.begin(), vY.end());
for(int x=0;x+1<n;x++){
pq.push({vX[x+1].first-vX[x].first, 0, x, x+1});
pq.push({vY[x+1].first-vY[x].first, 1, x, x+1});
}
while(k > 0 && !pq.empty()){
ll val = pq.top()[0], type = pq.top()[1], l = pq.top()[2], r = pq.top()[3];
pq.pop();
if(type == 0){
int idx1 = vX[l].second, idx2 = vX[r].second;
if(max(abs(p[idx2].first-p[idx1].first), abs(p[idx2].second-p[idx1].second)) == val){
cout << val << "\n";
k--;
}
if(r+1 < n){
pq.push({p[vX[r+1].second].first-p[vX[l].second].first, 0, l, r+1});
}
} else {
int idx1 = vY[l].second, idx2 = vY[r].second;
if(abs(p[idx2].first-p[idx1].first) < abs(p[idx2].second-p[idx1].second) && abs(p[idx2].second-p[idx1].second) == val){
cout << val << "\n";
k--;
}
if(r+1 < n){
pq.push({p[vY[r+1].second].second-p[vY[l].second].second, 1, l, r+1});
}
}
}
return 0;
}
