#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
const int mod = 1e16;
struct node{
vector<pair<int, int> > v;
};
vector<int> a;
vector<int> ALL;
int fl;
int FX, FY;
struct ST{
int n;
vector<node> tree;
ST(int sz){
n = sz;
tree.resize(n * 4);
for(int i = 0;i < n * 4; i++){
tree[i] = {};
}
}
node connect(node A, node B){
node res;
res.v = {};
merge(all(A.v), all(B.v), back_inserter(res.v));
return res;
}
void build(int v, int vl, int vr, vector<int> &b){
if(vl == vr){
tree[v].v = {{b[vl], vl}};
}else{
int mid = (vl + vr)>>1;
build(v<<1, vl, mid, b);
build(v<<1|1, mid+1, vr,b);
tree[v] = connect(tree[v<<1], tree[v<<1|1]);
}
}
node get(int l, int r, int v, int vl, int vr){
if(l > vr or vl > r) return {};
if(l <= vl and r >= vr){
return tree[v];
}
int mid = (vl + vr)>>1;
return connect(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
}
int cnt_small(int l, int r, int x, int y, int v, int vl, int vr){
if(l > vr or vl > r) return 0LL;
if(l <= vl and r >= vr){
int it = upper_bound(all(tree[v].v), make_pair(y, mod)) - tree[v].v.begin();
int it1 = upper_bound(all(tree[v].v), make_pair(x - 1, mod)) - tree[v].v.begin();
if(fl){
for(int i = it1; i < it; i++){
int idx = tree[v].v[i].ss;
ALL.push_back(max(abs(tree[v].v[i].ff - FY), abs(a[idx] - FX)));
}
}
return it - it1;
}
int mid = (vl + vr)>>1;
return cnt_small(l, r, x, y, v<<1, vl, mid) + cnt_small(l, r, x, y, v<<1|1, mid+1, vr);
}
};
int n, k;
int calc(vector<pair<int, int> > &v, int sum, ST &seg){
int cnt = 0;
for(int i = 1;i <= n; i++){
int x = v[i].ff, y = v[i].ss;
int r = i-1, l = lower_bound(all(a), x - sum) - a.begin();
if(l > r){
continue;
}
int fn = y - sum, fn1 = y + sum;
int smaller = seg.cnt_small(l, r, fn, fn1, 1, 1, n);
cnt = cnt + smaller;
}
return cnt;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> k;
vector<pair<int, int> > v(n + 1);
v[0] = {INT_MIN, INT_MIN};
for(int i = 1;i <= n; i++){
cin >> v[i].ff >> v[i].ss;
int x = v[i].ff, y = v[i].ss;
v[i].ff = x - y;
v[i].ss = x + y;
}
sort(all(v), [&](auto A, auto B){
return A.ff < B.ff;
});
ST seg(n+1);
vector<int> b(n + 1);
a.resize(n+1);
a[0] = INT_MIN;
for(int i = 1;i <= n; i++){
b[i] = v[i].ss;
a[i] = v[i].ff;
}
seg.build(1, 1, n, b);
int l = 0, r = (int)1e10;
while(l + 1 < r){
int mid = (l + r)>>1;
int CNT = calc(v, mid, seg);
if(CNT > k) r = mid;
else l = mid;
}
l = r;
fl = 1;
for(int i = 1;i <= n; i++){
int x = v[i].ff, y = v[i].ss;
int rr = i-1, ll = lower_bound(all(a), x - l) - a.begin();
if(ll > rr){
continue;
}
FX = x, FY = y;
int fn = y - l, fn1 = y + l;
int smaller = seg.cnt_small(ll, rr, fn, fn1, 1, 1, n);
}
sort(all(ALL));
while((int)ALL.size() > k) ALL.pop_back();
for(int x : ALL) cout << x << '\n';
return 0;
}
