#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;
int fw[1000005];
int n,k;
void upd(int x, int y){
while(x<1000005){
fw[x]+=y;
x+=x&(-x);
}
}
int sum(int x){
int counter=0;
while(x>0){
counter+=fw[x];
x-=x&(-x);
}
return counter;
}
void rangeUpd(int x, int y, int c){
x=max(x,1LL);
y=min(y,1000000LL);
upd(x,c);
upd(y+1,-c);
}
void solve(){
cin >> n >> k;
pii arr[n];
for(int x=0;x<n;x++){
cin >> arr[x].first >> arr[x].second;
int a=arr[x].first+arr[x].second;
int b=arr[x].first-arr[x].second;
arr[x].first=a;
arr[x].second=b;
//show2(a,a,b,b);
}
sort(arr,arr+n);
int l=0;
int r=4e9;
int mid;
int best=r;
while(l<=r){
//show2(l,l,r,r);
mid=(l+r)/2;
int counter=0;
vector<array<int,4>>v;
vector<int>dis;
for(int x=0;x<n;x++){
int a=arr[x].first;
int b=arr[x].second;
v.push_back({a-mid,0,b-mid,b+mid});
v.push_back({a,1,b,b});
dis.push_back(b-mid);
dis.push_back(b+mid);
dis.push_back(b);
}
sort(v.begin(),v.end());
//for(auto it:v){
//cout << it[0] << " " << it[1] << " " << it[2] << " " << it[3] << endl;
//}
sort(dis.begin(),dis.end());
dis.resize(unique(dis.begin(),dis.end())-dis.begin());
int ptr=0;
memset(fw,0,sizeof(fw));
int sz=v.size();
//show4(dis,dis);
for(int x=0;x<sz;x++){
v[x][2]=lower_bound(dis.begin(),dis.end(),v[x][2])-dis.begin()+1;
v[x][3]=lower_bound(dis.begin(),dis.end(),v[x][3])-dis.begin()+1;
//show3(v[x][1],v[x][1],v[x][2],v[x][2],v[x][3],v[x][3]);
while(ptr<sz&&v[x][0]-2*mid>v[ptr][0]){
if(v[ptr][1]==0){
rangeUpd(v[ptr][2],v[ptr][3],-1);
}
ptr++;
}
if(v[x][1]==0){
rangeUpd(v[x][2],v[x][3],1);
}
else{
counter+=sum(v[x][2]);
}
//show(counter,counter);
}
counter=(counter-n)/2;
//show(counter,counter);
if(counter>=k){
best=mid;
r=mid-1;
}
else l=mid+1;
}
//show(best,best);
vector<int>ans;
multiset<pii>se;
int ptr2=0;
for(int x=0;x<n;x++){
while(ptr2<n&&arr[ptr2].first<arr[x].first-best){
se.erase(se.find({arr[ptr2].second,arr[ptr2].first}));
ptr2++;
}
//show3(x,x,arr[x].first,arr[x].first,arr[x].second,arr[x].second);
auto rt=se.lower_bound({arr[x].second,1e15});
auto cur=rt;
while(cur!=se.end()){
pii hold=*cur;
if(hold.first>arr[x].second+best) break;
ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
//show2(hold.first,hold.first,hold.second,hold.second);
cur++;
}
cur=rt;
while(cur!=se.begin()){
cur--;
pii hold=*cur;
if(hold.first<arr[x].second-best) break;
ans.push_back(max(abs(hold.first-arr[x].second),abs(hold.second-arr[x].first)));
//show2(hold.first,hold.first,hold.second,hold.second);
}
se.insert({arr[x].second,arr[x].first});
}
sort(ans.begin(),ans.end());
for(int x=0;x<k;x++){
cout << ans[x] << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
