#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for(int i=0; i<n; ++i)
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
struct BIT {
vector<int> t; int n;
BIT(int n) {
t.assign(n,0); this->n=n;
}
void add(int i, int x) {
for(;i<n;i|=i+1) t[i]+=x;
}
int sum(int r) {
int q=0;
for(;r>=0;r=(r&(r+1))-1) q+=t[r];
return q;
}
};
void solve() {
int n,k; cin>>n>>k;
vector<pi> a(n);
forn(i,n) cin>>a[i].f>>a[i].s;
vector<pi> f,s;
forn(i,n) {
f.pb({a[i].f+a[i].s,i});
}
sort(all(f));
forn(i,n) {
int j=f[i].s;
s.pb({a[j].f-a[j].s,i});
}
sort(all(s));
//forn(i,n) cout<<f[i].f<<','<<f[i].s<<" "; cout<<'\n';
//forn(i,n) cout<<s[i].f<<','<<s[i].s<<" "; cout<<'\n';
int l=1, r=4e9;
while (l<r) {
int m=(l+r+1)>>1;
int lx=0,rx=0;
BIT ft(n);
int z = 0;
forn(i,n) {
while (rx<n && s[rx].f<=s[i].f+m) {
//cout<<"> "<<m<<' '<<i<<": "<<rx<<' '<<s[i].f<<' '<<s[rx].f<<'\n';
ft.add(s[rx].s,1); ++rx;
}
while (s[lx].f < s[i].f-m) {
ft.add(s[lx].s,-1); ++lx;
}
int j = s[i].s;
int ls=0, rs=n-1;
while (ls<rs) {
int ms=(ls+rs)>>1;
if (f[ms].f < f[j].f-m) ls=ms+1;
else rs=ms;
}
int lq = rs;
ls=0, rs=n-1;
while (ls<rs) {
int ms=(ls+rs+1)>>1;
if (f[ms].f > f[j].f+m) rs=ms-1;
else ls=ms;
}
int rq = rs;
//cout<<"! "<<i<<' '<<f[j].s+1<<" "<<lx<<" "<<rx<<" "<<lq<<' '<<rq<<' '<<ft.sum(rq)-ft.sum(lq-1)-1<<'\n';
z+=ft.sum(rq) - ft.sum(lq-1) - 1;
}
z>>=1;
//cout<<"? "<<m<<": "<<z<<'\n';
if (z >= k) r=m-1;
else l=m;
}
vector<int> ans;
int m = r;
set<int> st;
int lx=0,rx=0;
forn(i,n) {
while (rx<n && s[rx].f<=s[i].f+m) {
st.insert(s[rx].s); ++rx;
}
while (lx<i) {
st.erase(s[lx].s); ++lx;
}
int j = s[i].s;
int ls=0, rs=n-1;
while (ls<rs) {
int ms=(ls+rs)>>1;
if (f[ms].f < f[j].f-m) ls=ms+1;
else rs=ms;
}
int lq = rs;
ls=0, rs=n-1;
while (ls<rs) {
int ms=(ls+rs+1)>>1;
if (f[ms].f > f[j].f+m) rs=ms-1;
else ls=ms;
}
int rq = rs;
int j1 = f[j].s;
auto it = st.lower_bound(lq);
while (it!=st.end()) {
int jj = *it;
if (jj>rq) break;
int j2 = f[jj].s;
if (j1==j2) {++it; continue;}
int d = abs(a[j1].f-a[j2].f)+abs(a[j1].s-a[j2].s);
ans.pb(d);
++it;
}
}
sort(all(ans));
while (ans.size()<k) ans.pb(m+1);
for(auto&x:ans) cout<<x<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//int t; cin>>t; while (t--)
solve();
}
