#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(int _t,int _typ,int _l,int _r,int _i){t = _t;typ = _typ;l = _l;r = _r;i = _i;};
int 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<pair<ll,int>> segTree;
vector<ll> a;
void build(int l,int r,int indV)
{
if(l == r)
{
segTree[indV] = {a[l],l};
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,l};
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]);
}
pair<ll,int> get(int lx,int rx,int l,int r,int indV)
{
if(l > rx || r < lx)
return {-INF,-1};
else if(l >= lx && r <= rx)
return segTree[indV];
int m = (l+r)/2;
pair<ll,int> sl = get(lx,rx,l,m,indV*2+1);
pair<ll,int> sr = get(lx,rx,m+1,r,indV*2+2);
return max(sl,sr);
}
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)
{
// cout << i << ' ' << j << ' ' << abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second) << "\n";
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<ll>> ts(n);
vector<int> po(n,-1);
vector<ll> ans;
a.clear();
a.resize(n);
for(int i = 0;i < n;++i)
{
a[i] = -INF;
}
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);
po[events[i].l] ++;
a[events[i].l] = events[i].t;
modify(events[i].l,a[events[i].l],0,n-1,0);
}
else
{
set<int> ch;
while(true)
{
pair<ll,int> tk = get(events[i].l,events[i].r,0,n-1,0);
if(tk.first < p2[events[i].i].first - d)
break;
ans.push_back(dist(events[i].i,ts[tk.second][po[tk.second]]));
if(events[i].i == ts[tk.second][po[tk.second]])
{
ans.pop_back();
ch.insert(tk.second);
modify(tk.second,-INF,0,n-1,0);
}
else
{
if(ans.size() == k)
{
break;
}
ch.insert(tk.second);
po[tk.second]--;
modify(tk.second,(po[tk.second] == -1 ? -INF : p2[ts[tk.second][po[tk.second]]].first),0,n-1,0);
}
}
if(ans.size() == k)
break;
for(auto y:ch)
{
po[y] = int(ts[y].size())-1;
modify(y,a[y],0,n-1,0);
}
}
}
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";
}
