#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=250030;
const int mxM=500004;
const int MOD=998244353;
const ll INF=8e18;
typedef struct qry{
int typ;
ll y, x1, x2;
int ix;
qry() : typ(), y(), x1(), x2(), ix() {}
qry(int typ, ll y, ll x1, ll x2) : typ(typ), y(y), x1(x1), x2(x2), ix(){}
qry(int typ, ll y, ll x1, ll x2, int ix) : typ(typ), y(y), x1(x1), x2(x2), ix(ix){}
bool operator<(qry a){
if(a.y!=y) return y<a.y;
return typ<a.typ;
}
}qry;
typedef struct BIT{ ///zero indexed
int fen[mxN], n;
void set_n(int m){n=m;}
void init(){for(int i=0;i<=n;i++) fen[i]=0;}
void upd(int i){i++; for(;i<=n;i+=(i&(-i))) fen[i]++;}
int sum(int i){int res=0; for(;i>0;i-=(i&(-i))) res+=fen[i]; return res;}
int solv(int s, int e){s++; e++; return sum(e)-sum(s-1);}
}BIT;
typedef struct segtree{
set <int> seg[4*mxN];
void upd(int idx, int s1, int e1, int s2, int e2, int val, int typ){
if(s2>e1 || s1>e2) return;
if(s2<=s1 && e1<=e2){
if(typ==1) seg[idx].insert(val);
else seg[idx].erase(val);
return;
}
int mid=(s1+e1)/2;
upd(2*idx, s1, mid, s2, e2, val, typ);
upd(2*idx+1, mid+1, e1, s2, e2, val, typ);
}
void solv(int idx, int s1, int e1, int pos, vector <int> &v){
for(int ele : seg[idx]) v.push_back(ele);
if(s1==e1) return;
int mid=(s1+e1)/2;
if(pos<=mid) solv(2*idx, s1, mid, pos, v);
else solv(2*idx+1, mid+1, e1, pos, v);
}
}segtree;
int N, K;
pll A[mxN];
vector <ll> crx, cry;
BIT T1;
segtree T2;
void input(){
cin >> N >> K;
for(int i=1;i<=N;i++) cin >> A[i].fi >> A[i].se, A[i]=pll(A[i].fi+A[i].se, A[i].fi-A[i].se);
}
void compress(vector <ll> &v){
sort(all(v));
v.erase(unique(all(v)), v.end());
}
void make_coor(){
for(int i=1;i<=N;i++){
auto [x, y]=A[i];
crx.push_back(x);
cry.push_back(y);
}
compress(crx);
compress(cry);
for(int i=1;i<=N;i++){
auto &[x, y]=A[i];
x=lower_bound(all(crx), x)-crx.begin();
y=lower_bound(all(cry), y)-cry.begin();
}
}
ll solv1(ll d){
ll res=0;
vector <qry> ct; ///1: add point, 2: minus 구간, 3: plus 구간
T1.set_n(crx.size());
T1.init();
for(int i=1;i<=N;i++){
auto [x, y]=A[i];
ll ulx, dlx, uly, dly;
ulx=upper_bound(all(crx), crx[x]+d)-crx.begin()-1;
uly=upper_bound(all(cry), cry[y]+d)-cry.begin()-1;
dlx=lower_bound(all(crx), crx[x]-d)-crx.begin();
dly=lower_bound(all(cry), cry[y]-d)-cry.begin();
if(dly!=0) ct.emplace_back(2, dly-1, dlx, ulx);
ct.emplace_back(3, uly, dlx, ulx);
ct.emplace_back(1, y, x, x);
}
sort(all(ct));
for(auto [typ, y, x1, x2, _] : ct)
{
if(typ==1){
T1.upd(x1);
}
else{
int sgn=(typ==2 ? -1 : 1);
int val=T1.solv(x1, x2);
res+=sgn*val;
}
}
return (res-N)/2;
}
ll dist(int a, int b)
{
pll na=pll(crx[A[a].fi], cry[A[a].se]);
pll nb=pll(crx[A[b].fi], cry[A[b].se]);
return max(abs(na.fi-nb.fi), abs(na.se-nb.se));
}
void solv2(ll d){
vector <ll> dis;
vector <qry> ct; ///1: add 구간, 2: delete 구간, 3: add point
for(int i=1;i<=N;i++){
auto [x, y]=A[i];
ll ulx, dlx, uly, dly;
ulx=upper_bound(all(crx), crx[x]+d)-crx.begin()-1;
uly=upper_bound(all(cry), cry[y]+d)-cry.begin()-1;
dlx=lower_bound(all(crx), crx[x]-d)-crx.begin();
dly=lower_bound(all(cry), cry[y]-d)-cry.begin();
ct.emplace_back(1, dly, dlx, ulx, i);
if(uly+1!=cry.size()) ct.emplace_back(2, uly+1, dlx, ulx, i);
ct.emplace_back(3, y, x, x, i);
}
sort(all(ct));
for(auto [typ, y, x1, x2, ix] : ct)
{
if(typ<=2){
T2.upd(1, 0, crx.size()-1, x1, x2, ix, typ);
}
else{
vector <int> nv;
T2.solv(1, 0, crx.size()-1, x1, nv);
for(int ele : nv) if(ele>ix) dis.push_back(dist(ele, ix));
}
}
sort(all(dis));
for(int i=0;i<K;i++) cout << dis[i] << '\n';
}
int main()
{
gibon
input();
make_coor();
ll s=0, e=4'000'000'001;
while(s!=e)
{
ll mid=(s+e)/2;
if(solv1(mid)>=K) e=mid;
else s=mid+1;
}
solv2(s);
}
