#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
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){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;
ll dist(int i,int j)
{
return abs(p[i].first-p[j].first) + abs(p[i].second-p[j].second);
}
vector<ll> check(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 = lower_bound(py.begin(),py.end(),make_pair(p2[i].second - d,ll(-1))) - py.begin();
int rg = 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));
}
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();
}
if(ans.size() == k)
{
break;
}
ch.insert(tk.second);
po[tk.second]--;
modify(tk.second,(po[tk.second] == -1 ? -INF : ts[tk.second][po[tk.second]]),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;
}
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;
for(int j = 0;j < n;++j)
pc[py[j].second].second = j;
ll l = 0,r = 1e10;
while(l < r)
{
int m = (l+r)/2;
vector<ll> ans = check(m,2*k);
if(ans.size() < 2*k)
l = m+1;
else
r = m;
}
vector<ll> ans = check(l-1,2*k);
sort(ans.begin(),ans.end());
for(int j = 0;j < ans.size();j+=2)
{
cout << ans[j] << "\n";
}
for(int j = 0;j < (k-ans.size()/2);++j)
{
cout << l << "\n";
}
cout << "\n";
}
