#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
#define comp(v) v.erase(unique(all(v)),v.end())
#define LB(i,v) lower_bound(all(v),i)-v.begin() // 1-based
#define UB(i,v) upper_bound(all(v),i)-v.begin()
#define fi first
#define se second
using namespace std;
typedef long long ll;
int N,K,YS;
ll X[1000001],Y[1000001];
struct dot{
ll x,y,id;
bool operator<(const dot &r) const{
if(x==r.x) return id<r.id;
return x<r.x;
}
} A[1000001];
vector<ll> xl,yl;
ll inf = 1e18;
ll ab(ll x){ return x<0?-x:x;}
struct Node{
int val;
int l,r;
} def = {0,0,0};
struct PST{
Node node[10000001];
int sz = 1;
int root[1000001];
void update(int now , int prv, int s, int e, int f, int x){
if(s==e) {node[now].val = node[prv].val + x; return; }
int m = s+e>>1;
if(f<=m){
node[now].l = sz; node[now].r = node[prv].r;
sz++;
update(node[now].l,node[prv].l,s,m,f,x);
}
else{
node[now].r = sz; node[now].l = node[prv].l;
sz++;
update(node[now].r,node[prv].r,m+1,e,f,x);
}
node[now].val = node[node[now].l].val+node[node[now].r].val;
}
int l,r;
int query(int now ,int prv, int s, int e){
if(l<=s && e<=r) return node[now].val-node[prv].val;
if(s>r || e<l) return 0;
int m = s+e>>1;
return query(node[now].l,node[prv].l,s,m)+query(node[now].r,node[prv].r,m+1,e);
}
} pst;
void init(){
forf(i,1,N){
pst.root[i] = pst.sz; pst.sz++;
pst.update(pst.root[i],pst.root[i-1],1,YS,LB(A[i].y,yl)+1,1);
}
}
ll findmin(ll x, ll y , int xs , int count){
ll l = 0;
ll r = 4*1e9;
ll m;
int pys,pye,pxe;
int s;
while(l+1<r){
m = l+r>>1;
int ys = LB(y-m,yl) + 1;
int ye = UB(y+m,yl)-1 + 1;
int xe = UB(x+m,xl)-1 + 1;
if(pys == ys && pye == ye && pxe == xe){
if(s==1) r=m;
else l=m;
}
pys=ys; pye=ye; pxe=xe;
pst.l = ys; pst.r = ye;
int tmp = pst.query(pst.root[xe],pst.root[xs],1,YS);
if(tmp >= count){r=m; s=1;}
else {l=m; s =0;}
}
return r;
}
int cnt[1000001];
void solve(){
init();
priority_queue<pair<ll,int> > pq;
forf(i,1,N) cnt[i] = 1;
forf(i,1,N){
pq.push({-findmin(A[i].x,A[i].y,i,cnt[i]) , i});
cnt[i]++;
}
forf(trash,1,K) {
printf("%lld\n", -pq.top().first);
int i = pq.top().second;
pq.pop();
pq.push({-findmin(A[i].x,A[i].y,i,cnt[i]) , i});
cnt[i]++;
}
}
vector<ll> All;
void naive(){
forf(i,1,N){
forf(j,i+1,N){
All.push_back(max(ab(X[i]-X[j]),ab(Y[i]-Y[j])));
}
}
sort(all(All));
forf(i,0,K-1) printf("%lld\n" , All[i]);
}
int main(){
scanf("%d %d" , &N,&K);
forf(i,1,N) scanf("%lld %lld" , &X[i] , &Y[i]);
forf(i,1,N){
ll x = X[i], y = Y[i];
X[i] = x+y;
Y[i] = x-y;
A[i] = {X[i],Y[i],i};
yl.push_back(Y[i]);
xl.push_back(X[i]);
}
sort(all(yl)); comp(yl); YS=yl.size();
sort(all(xl));
sort(A+1,A+N+1);
solve();
}
