#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
vector<ll> fenv;
void modifyf(int i,ll x)
{
for(int j = i;j < fenv.size();j += (j & (-j)))
fenv[j] += x;
return ;
}
ll getf(int r)
{
ll ans = 0;
for(int j = r;j > 0;j -= (j & (-j)))
ans += fenv[j];
return ans;
}
struct event
{
event(ll _t,int _typ,int _l,int _r,int _i){t = _t;typ = _typ;l = _l;r = _r;i = _i;};
ll t;
int typ;
int l,r;
int i;
bool operator < (const event & oth)const {return (t != oth.t ? t < oth.t : typ < oth.typ);};
};
vector<ll> segTree;
void build(int l,int r,int indV)
{
if(l == r)
{
segTree[indV] = -INF;
return ;
}
int m =(l+r)/2;
build(l,m,indV*2+1);
build(m+1,r,indV*2+2);
segTree[indV] = max(segTree[indV*2+1],segTree[indV*2+2]);
return;
}
void modify(int i,ll x,int l,int r,int indV)
{
if(l > i || r < i)
return ;
else if(l == r)
{
segTree[indV] = x;
return ;
}
int m = (l+r)/2;
modify(i,x,l,m,indV*2+1);
modify(i,x,m+1,r,indV*2+2);
segTree[indV] = max(segTree[indV*2+1],segTree[indV*2+2]);
}
vector<int> pos;
void get(int lx,int rx,int x,int l,int r,int indV)
{
if(l > rx || r < lx || (l >= lx && r <= rx && segTree[indV] < x))
return ;
else if(l == r)
{
pos.push_back(l);
return ;
}
int m = (l+r)/2;
get(lx,rx,x,l,m,indV*2+1);
get(lx,rx,x,m+1,r,indV*2+2);
return ;
}
vector<pair<ll,ll>> p;
vector<pair<ll,ll>> p2;
vector<pair<ll,ll>> pc;
vector<pair<ll,ll>> py;
vector<int> ind;
ll dist(int i,int j)
{
return abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second);
}
vector<ll> find_answer(ll d,ll k)
{
int n = p.size();
segTree.clear();
segTree.resize(4*p.size());
vector<event> events;
for(int i = 0;i < n;++i)
{
events.push_back(event(p2[i].first,0,pc[i].second,pc[i].second,i));
int lg = ind[lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin()];
int rg = ind[upper_bound(py.begin(),py.end(),make_pair(p2[i].second,ll(p.size())+1)) - py.begin()-1];
events.push_back(event(p2[i].first + d,1,lg,rg,i));
}
sort(events.begin(),events.end());
vector<vector<int>> ts(n);
vector<ll> ans;
build(0,n-1,0);
for(int i = 0;i < events.size();++i)
{
if(events[i].typ == 0)
{
ts[events[i].l].push_back(events[i].i);
modify(events[i].l,events[i].t,0,n-1,0);
}
else
{
pos.clear();
get(events[i].l,events[i].r,events[i].t - 2*d,0,n-1,0);
for(auto ti : pos)
{
for(int y = ts[ti].size()-1;y >= 0;--y)
{
if(dist(events[i].i,ts[ti][y]) <= k && events[i].i != ts[ti][y])
{
ans.push_back(dist(events[i].i,ts[ti][y]));
}
else
break;
}
}
}
}
return ans;
}
ll check(ll d,ll k)
{
int n = p.size();
fenv.clear();
fenv.resize(n+2);
vector<event> events;
for(int i = 0;i < n;++i)
{
events.push_back(event(p2[i].first,0,pc[i].second,pc[i].second,i));
int lg = ind[lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin()];
int rg = ind[upper_bound(py.begin(),py.end(),make_pair(p2[i].second + d,ll(p.size())+1)) - py.begin()-1];
events.push_back(event(p2[i].first + d,1,lg,rg,i));
events.push_back(event(p2[i].first - d,-1,lg,rg,i));
}
sort(events.begin(),events.end());
ll ans = 0;
for(int i = 0;i < events.size();++i)
{
if(events[i].typ == 0)
{
ans += getf(events[i].l+1);
}
else if(events[i].typ == -1)
{
modifyf(events[i].l+1,1);
modifyf(events[i].r+2,-1);
}
else
{
modifyf(events[i].l+1,-1);
modifyf(events[i].r+2,1);
}
}
return (ans-n)/2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n,k;
cin >> n >> k;
for(int j = 0;j < n;++j)
{
ll x,y;
cin >> x >> y;
p.push_back({x,y});
p2.push_back({x+y,x-y});
py.push_back({x-y,j});
}
sort(py.begin(),py.end());
pc = p2;
int ty = 0;
for(int j = 0;j < n;++j)
{
if(j > 0 && py[j].first != py[j-1].first)
ty++;
pc[py[j].second].second = ty;
ind.push_back(ty);
}
ll l = 0,r = 4e9;
while(l < r)
{
ll m = (l+r)/2;
vector<ll> ans = find_answer(m,k);
if(ans.size() < k)
l = m+1;
else
r = m;
}
vector<ll> ans = find_answer(l-1,k);
sort(ans.begin(),ans.end());
for(int j = 0;j < ans.size();j++)
{
cout << ans[j] << "\n";
}
for(int j = 0;j < (k-ans.size());++j)
{
cout << l << "\n";
}
cout << "\n";
}
