#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG
const ll maxn=2e5+5e4+5;
const ll inf=1e15;
const ll mod=1e9+7;
ll n;
ll x[maxn],y[maxn];
ii ranges[maxn];
vector<ll> pos;
vector<ii> updates;
ll fen[maxn];
void upd(ll x, ll v){
while (x<maxn){
fen[x]+=v;
x+=(x&-x);
}
}
ll query(ll x){
ll ans=0;
while (x){
ans+=fen[x];
x-=(x&-x);
}
return ans;
}
ll query(ll x, ll y){
return query(y)-query(x-1);
}
ll check(ll len){
vector<tuple<ll,ll,ll>> queries;
for (int i=1;i<=n;i++){
queries.emplace_back(y[i]-len-1,i,-1);
//exclusive
queries.emplace_back(y[i]+len,i,1);
//inclusive
ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
-pos.begin();
ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
-pos.begin()-1;
}
sort(queries.begin(),queries.end());
ll ans=0,ptr=0;
memset(fen,0,sizeof(fen));
for (auto [a,b,c]:queries){
while (ptr!=updates.size() &&
updates[ptr].first<=a){
upd(updates[ptr].second,1);
ptr++;
}
ans+=c*(query(ranges[b].first,ranges[b].second));
}
return (ans-n)/2;
}
struct node{
ll s,e,m;
vector<ii> v;
node *l,*r;
node(ll _s, ll _e){
s=_s,e=_e,m=(s+e)>>1;
if (s!=e) l=new node(s,m),r=new node(m+1,e);
}
void upd(ll x, ii p){
if (s==e){
v.emplace_back(p);
return;
}
if (x>m) r->upd(x,p);
else l->upd(x,p);
}
void build(){
if (s!=e){
l->build(),r->build();
for (auto u:l->v) v.emplace_back(u);
for (auto u:r->v) v.emplace_back(u);
}
sort(v.begin(),v.end()); //remember to put y first
}
vector<ll> query(ll x, ll y, ll v1, ll v2, ii p){
if (x<=s && e<=y){
ll x1,y1;
tie(y1,x1)=p;
ll lb=lower_bound(v.begin(),v.end(),
make_pair(v1,-inf))-v.begin();
ll ub=upper_bound(v.begin(),v.end(),
make_pair(v2,inf))-v.begin();
vector<ll> out;
for (int i=lb;i<ub;i++){
ll x2,y2;
tie(y2,x2)=v[i];
if (x1==x2 && y1==y2) continue;
out.emplace_back(max(abs(x1-x2),abs(y1-y2)));
}
return out;
}
if (x>m) return r->query(x,y,v1,v2,p);
if (y<=m) return l->query(x,y,v1,v2,p);
vector<ll> out1=l->query(x,y,v1,v2,p);
vector<ll> out2=r->query(x,y,v1,v2,p);
for (auto u:out1) out2.emplace_back(u);
return out2;
}
}*root;
ll flat[maxn];
vector<ll> out;
void solve(ll len){
for (int i=1;i<=n;i++){
ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
-pos.begin();
ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
-pos.begin()-1;
}
root=new node(1,n);
for (int i=1;i<=n;i++){
root->upd(flat[i],make_pair(y[i],x[i]));
}
root->build();
for (int i=1;i<=n;i++){
ll l,r;
tie(l,r)=ranges[i];
vector<ll> roads=root->query(l,r,y[i]-len,
y[i]+len,make_pair(y[i],x[i]));
//left x, right x, bottom y, top y, central point
for (auto u:roads) out.emplace_back(u);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll a,b,k;
cin>>n>>k;
for (int i=1;i<=n;i++){
cin>>a>>b;
x[i]=a+b,y[i]=a-b;
pos.emplace_back(x[i]);
}
pos.emplace_back(-inf);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
for (int i=1;i<=n;i++){
flat[i]=lower_bound(pos.begin(),pos.end(),x[i])
-pos.begin();
updates.emplace_back(y[i],flat[i]);
}
sort(updates.begin(),updates.end());
ll l=1,r=4'000'000'005,m;
while (l!=r-1){
m=(l+r)>>1;
if (check(m)>=k) r=m; //we need to reach r
else l=m;
}
//find everything <=l
solve(l);
sort(out.begin(),out.end());
while (out.size()<2*k) out.emplace_back(r);
for (int i=0;i<out.size();i+=2) cout<<out[i]<<endl;
return 0;
}
