#include <bits/stdc++.h>
using namespace std;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 3e5 + 5;
vector<array<int,2>> ys;
int gety (array<int,2> y) {return lower_bound(ys.begin(),ys.end(),y) - ys.begin() + 1;}
int total,k; vector<long long> ret;
struct Seg {
long long tree[MN<<2];
void clear() {memset(tree,0x3f,sizeof tree);}
void update (int ind, int tl, int tr, int i, long long v) {
if (tl == tr) {
tree[ind] = v;
return;
}
int mid = (tl + tr) / 2;
if (i <= mid) update(lc,tl,mid,i,v);
else update(rc,mid+1,tr,i,v);
tree[ind] = min(tree[lc],tree[rc]);
}
void walk (int ind, int tl, int tr, int l, int r, long long v) { //find all vertices with value <= v
if (tree[ind] > v) return;
if (tl == tr) {
++total;
return;
}
int mid = (tl + tr) / 2;
if (tree[lc] <= v && l <= mid) walk(lc,tl,mid,l,r,v);
if (tree[rc] <= v && r > mid) walk(rc,mid+1,tr,l,r,v);
}
void get (int ind, int tl, int tr, int l, int r, long long v, long long add) { //find all vertices with value <= v
if (tree[ind] > v) return;
if (tl == tr) {
ret.push_back(tree[ind]+add);
return;
}
int mid = (tl + tr) / 2;
if (tree[lc] <= v && l <= mid) get(lc,tl,mid,l,r,v,add);
if (tree[rc] <= v && r > mid) get(rc,mid+1,tr,l,r,v,add);
}
} pseg, sseg;
int main () {
int n; scanf ("%d %d",&n,&k);
vector<array<int,2>> pts(n);
for (int i = 0; i < n; i++) scanf ("%d %d",&pts[i][0],&pts[i][1]);
sort(pts.begin(),pts.end());
for (int i = 0; i < n; i++) ys.push_back({pts[i][1],i});
sort(ys.begin(),ys.end());
auto check = [&] (long long mid) {
total = 0; pseg.clear(); sseg.clear();
for (int idx = 0; idx < n; idx++) {
auto &[x,y] = pts[idx];
int cmp = gety({y,idx});
pseg.walk(1,1,n,1,cmp,mid-x-y);
if (total >= k) break;
if (cmp < n) sseg.walk(1,1,n,cmp+1,n,mid+y-x);
if (total >= k) break;
pseg.update(1,1,n,cmp,-x-y);
sseg.update(1,1,n,cmp,y-x);
}
return total >= k;
};
auto get = [&] (long long mid) {
pseg.clear(); sseg.clear();
for (int idx = 0; idx < n; idx++) {
auto &[x,y] = pts[idx];
int cmp = gety({y,idx});
pseg.get(1,1,n,1,cmp,mid-x-y,x+y);
if (cmp < n) sseg.get(1,1,n,cmp+1,n,mid+y-x,x-y);
pseg.update(1,1,n,cmp,-x-y);
sseg.update(1,1,n,cmp,y-x);
}
};
long long low = 0, high = 4e9 + 1, mid, ans = -1;
while (low <= high) {
mid = (low + high) / 2;
if (check(mid)) high = (ans = mid) - 1;
else low = mid + 1;
}
get(ans-1);
sort(ret.begin(),ret.end());
while ((int)ret.size() < k) ret.push_back(ans);
for (long long x : ret) printf ("%lld\n",x);
return 0;
}
