#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class FT
{
public:
int N;
vector<int> a, f;
FT(vector<int> z)
{
N = z.size(); a = z; int sum = 0;
vector<int> ps; ps.pb(0); REP(i,0,N) {sum+=a[i]; ps.pb(sum);}
REP(i,0,N+1)
{
f.pb(ps[i] - ps[i-(i&(-i))]);
}
}
int sum(int s)
{
if(s<0) {return 0;}
int cur = s+1;
int ans = 0;
while(cur>0)
{
ans+=f[cur];
cur-=(cur&(-cur));
}
return ans;
}
void update(int s, int dif)
{
int cur = s+1;
a[s]+=dif;
while(cur<=N)
{
f[cur]+=dif;
cur+=(cur&(-cur));
}
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll N,K; cin>>N>>K;
vector<pl> P; pl cur; REP(i,0,N) {cin>>cur.ff>>cur.ss; P.pb(mp(cur.ff+cur.ss,cur.ss-cur.ff));}
sort(whole(P));
vector<ll> Yvals; REP(i,0,N) {Yvals.pb(P[i].ss);}
sort(whole(Yvals));
unordered_map<ll,ll> comp; ll c=0LL; vector<ll> key;
comp.reserve(1LL<<25LL); comp.max_load_factor(0.25);
REP(i,0,Yvals.size())
{
if(i!=0 && Yvals[i]==Yvals[i-1]) {continue;}
comp[Yvals[i]]=c; c++; key.pb(Yvals[i]);
}
ll lo = 1LL; ll hi = 5000000000LL;
vector<int> insig; REP(i,0,N) {insig.pb(0);}
while(lo<hi)
{
FT S(insig);
ll d=(lo+hi)/2LL;
ll cnt=0LL;
ll l=0LL; ll r=0LL;
S.update(comp[P[0].ss],1LL);
REP(ind,0,N)
{
ll x = P[ind].ff; ll y = P[ind].ss;
while(l<N && P[l].ff<x-d)
{
S.update(comp[P[l].ss],-1LL);
l++;
}
while(r<N && P[r].ff<=x+d)
{
r++;
if(r<N && P[r].ff<=x+d) {S.update(comp[P[r].ss],1LL);}
}
r--;
ll leftindex = (ll) (lower_bound(whole(key),y-d) - key.begin());
ll rightindex = (ll) (upper_bound(whole(key),y+d) - key.begin()) -1LL;
if(leftindex!=0) {cnt+=(S.sum(rightindex)-S.sum(leftindex-1LL));}
else {cnt+=S.sum(rightindex);}
cnt--;
}
cnt/=2LL;
if(cnt>=K) {hi=d;}
else {lo=d+1LL;}
}
ll d=lo-1LL;
vector<ll> ans;
map<ll,deque<ll> > m; deque<ll> xxxx;
int l=0; int r=0LL; m[P[0].ss]=xxxx; m[P[0].ss].pb(P[0].ff);
map<ll,deque<ll> >::iterator it; deque<ll>::iterator it2,it3;
REP(ind,0,N)
{
ll x = P[ind].ff; ll y = P[ind].ss;
while(l<N && P[l].ff<x-d)
{
m[P[l].ss].pop_front();
if(m[P[l].ss].size()==0) {m.erase(P[l].ss);}
l++;
}
while(r<N && P[r].ff<=x+d)
{
r++;
if(r<N && P[r].ff<=x+d) {if(m.find(P[r].ss)==m.end()) {m[P[r].ss]=xxxx;} m[P[r].ss].pb(P[r].ff);}
}
r--;
it=m.lower_bound(y-d);
while(it!=m.end() && it->ff<=y+d)
{
it2=(it->ss).begin(); it3=(it->ss).end();
ll dx,dy; dy = it->ff-y;
while(it2!=it3)
{
ll dx = (*it2)-x;
ans.pb(max(abs(dx),abs(dy)));
it2++;
}
it++;
}
}
sort(whole(ans)); while(ans.size()!=2LL*K+N) {ans.pb(lo);}
REP(i,0,ans.size())
{
if(ans[i]==0) {continue;}
if(i%2==0) {cout<<ans[i]<<"\n";}
}
return 0;
}
