#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const ll INF=3e18;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end());uni(c)
const ll C=4e9;
const int N=250005;
ll n,k;
vector<pll> p;
vector<ll> v;
struct BIT
{
ll sz,a[N];
void init()
{
rep1(i,sz) a[i]=0;
}
void upd(ll x,ll val)
{
for(;x<=sz;x+=x&-x) a[x]+=val;
}
ll qry(ll x)
{
ll ret=0;
for(;x;x-=x&-x) ret+=a[x];
return ret;
}
} bit;
ll calc(ll d)
{
ll ret=0;
ll l=0;
bit.init();
rep(i,n)
{
while(l<i&&p[i].F-p[l].F>d)
{
ll id=lower_bound(v.begin(),v.end(),p[l].S)-v.begin()+1;
bit.upd(id,-1);
l++;
}
ll ql=lower_bound(v.begin(),v.end(),p[i].S-d)-v.begin()+1;
ll qr=upper_bound(v.begin(),v.end(),p[i].S+d)-v.begin();
ret+=bit.qry(qr)-bit.qry(ql-1);
ll id=lower_bound(v.begin(),v.end(),p[i].S)-v.begin()+1;
bit.upd(id,1);
}
return ret;
}
void getans(ll d,ll k)
{
if(d==0)
{
rep(i,k) cout<<"0\n";
return;
}
vector<ll> ans;
multiset<pll> s;
ll l=0;
rep(i,n)
{
while(l<i&&p[i].F-p[l].F>d-1)
{
s.erase(s.find({p[l].S,p[l].F}));
l++;
}
auto qr=s.upper_bound({p[i].S+d-1,INF});
for(auto it=s.lower_bound({p[i].S-d+1,-INF});it!=qr;it++)
{
pll q=*it;
swap(q.F,q.S);
ans.pb(max(abs(q.F-p[i].F),abs(q.S-p[i].S)));
}
s.insert({p[i].S,p[i].F});
}
sort(ans.begin(),ans.end());
for(ll u:ans) cout<<u<<"\n";
ll r=k-ans.size();
rep(_,r) cout<<d<<"\n";
}
signed main()
{
MottoHayaku
cin>>n>>k;
rep(i,n)
{
ll X,Y;
cin>>X>>Y;
p.pb({X-Y,X+Y});
v.pb(X+Y);
}
unisort(v);
sort(p.begin(),p.end());
ll l=1,r=C;
bit.sz=v.size();
while(l<r)
{
ll mid=l+r>>1;
ll tmp=calc(mid);
if(tmp<k) l=mid+1;
else r=mid;
}
getans(l,k);
}
