#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int fen[250005];
void update(int i,int k){
while (i<250005){
fen[i]+=k;
i+=i&-i;
}
}
int query(int i){
int res=0;
while (i){
res+=fen[i];
i-=i&-i;
}
return res;
}
int query(int i,int j){
return query(j)-query(i-1);
}
vector<int> vq;
struct node{
int s,e,m;
set<int> idx;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void add(int i,int k){
idx.insert(k);
if (s==e) return;
else if (i<=m) l->add(i,k);
else r->add(i,k);
}
void rem(int i,int k){
idx.erase(k);
if (s==e) return;
else if (i<=m) l->rem(i,k);
else r->rem(i,k);
}
void query(int i,int j){
if (s==i && e==j){
for (auto it:idx) vq.pub(it);
}
else if (j<=m) l->query(i,j);
else if (m<i) r->query(i,j);
else l->query(i,m),r->query(m+1,j);
}
} *root=new node(0,250005);
int n,k;
ii arr[250005];
vector<int> uni={-(int)1e18}; //unique points in the y-direction
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>k;
rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
rep(x,1,n+1) arr[x]={arr[x].fi-arr[x].se,arr[x].fi+arr[x].se};
sort(arr+1,arr+n+1);
rep(x,1,n+1) uni.pub(arr[x].se);
sort(all(uni));
uni.erase(unique(all(uni)),uni.end());
int lo=0,hi=4e9+100,mi;
while (hi-lo>1){
mi=hi+lo>>1;
memset(fen,0,sizeof(fen));
int l=1,r=0; //[l,r]
int num=0;
rep(x,1,n+1){
while (r+1<=n && arr[r+1].fi<=arr[x].fi+mi){
r++;
int pos=lb(all(uni),arr[r].se)-uni.begin();
update(pos,1);
}
while (l<=n && arr[l].fi<arr[x].fi-mi){
int pos=lb(all(uni),arr[l].se)-uni.begin();
update(pos,-1);
l++;
}
int l=lb(all(uni),arr[x].se-mi)-uni.begin();
int r=ub(all(uni),arr[x].se+mi)-uni.begin()-1;
num+=query(l,r);
}
num=(num-n)/2;
if (num>=k) hi=mi;
else lo=mi;
}
vector<int> ans;
int l=1,r=0;
rep(x,1,n+1){
while (r+1<=n && arr[r+1].fi<=arr[x].fi+lo){
r++;
int pos=lb(all(uni),arr[r].se)-uni.begin();
root->add(pos,r);
}
while (l<=n && arr[l].fi<arr[x].fi-lo){
int pos=lb(all(uni),arr[l].se)-uni.begin();
root->rem(pos,l);
l++;
}
int l=lb(all(uni),arr[x].se-lo)-uni.begin();
int r=ub(all(uni),arr[x].se+lo)-uni.begin()-1;
vq.clear();
root->query(l,r);
for (auto it:vq) if (it<x){
ans.pub(max(abs(arr[x].fi-arr[it].fi),abs(arr[x].se-arr[it].se)));
}
}
while (sz(ans)<k) ans.pub(hi);
sort(all(ans));
for (auto it:ans) cout<<it<<endl;
}
