#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point{
int x,y,idx;
bool operator<(const point &t)const{
if (y!=t.y)
return y<t.y;
return x<t.x;
}
};
const int Tree_size=1<<18;
const ll INF=4e9;
int N,Cnt,Size;
ll K,Ans;
int Tree[Tree_size<<1],L[250001],R[250001];
point Point[250001];
vector<ll> Cor_X,Dist;
multiset<int> S[250001];
void init(){
for (register int i=1; i<(Tree_size<<1); i++)
Tree[i]=0;
}
void update(int idx,int v){
for (idx+=Tree_size; idx; idx>>=1)
Tree[idx]+=v;
}
int query(int l,int r){
int ret=0;
for (l+=Tree_size,r+=Tree_size; l<=r; l>>=1,r>>=1){
if (l&1)
ret+=Tree[l++];
if (!(r&1))
ret+=Tree[r--];
}
return ret;
}
ll f(ll m,bool flag){
ll ret=0;
init();
for (register int i=1,s=1; i<=N; i++){
while (Point[i].y-Point[s].y>m){
update(Point[s].idx,-1);
if (flag)
S[Point[s].idx].erase(S[Point[s].idx].find(Point[s].y));
s++;
}
int l=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x-m)-Cor_X.begin(),r;
auto it=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x+m);
if (it==Cor_X.end())
r=Size-1;
else if (*it==Point[i].x+m)
r=it-Cor_X.begin();
else
r=it-Cor_X.begin()-1;
if (l<=r)
ret+=query(l,r);
if (flag){
for (register int t=l; t<=r; t++){
for (int y:S[t]){
Dist.push_back(max(abs((ll)Point[i].x-Cor_X[t]),(ll)Point[i].y-y));
Cnt--;
}
}
S[Point[i].idx].insert(Point[i].y);
}
update(Point[i].idx,1);
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N>>K;
for (int i=1; i<=N; i++){
int x,y;
cin>>x>>y;
Point[i]={x+y,x-y};
Cor_X.push_back(Point[i].x);
}
sort(Point+1,Point+N+1);
sort(Cor_X.begin(),Cor_X.end());
Cor_X.erase(unique(Cor_X.begin(),Cor_X.end()),Cor_X.end());
Size=Cor_X.size();
for (int i=1; i<=N; i++)
Point[i].idx=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x)-Cor_X.begin();
ll l=0,r=INF;
while (l<=r){
ll m=(l+r)>>1;
if (f(m,false)>=K){
Ans=m;
r=m-1;
}
else
l=m+1;
}
Cnt=K;
f(Ans-1,true);
sort(Dist.begin(),Dist.end());
for (ll i:Dist)
cout<<i<<"\n";
while (Cnt--)
cout<<Ans<<"\n";
return 0;
}
