#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
struct Fenw{
vector <int> fenw;
int n;
Fenw(int n) : fenw(n + 1, 0), n(n) {}
void upd(int i, int val){
for (; i <= n; i += i & -i ){
fenw[i] += val;
}
}
int get(int i){
int cnt = 0;
for (; i > 0; i -= i & -i ){
cnt += fenw[i];
}
return cnt;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
vector <int> ans;
int X, Y, L_, R_;
struct SegTree{
vector <vector<ar<int,2>>> T;
int n;
SegTree(auto &a){
n = a.size();
T.resize(n * 4 + 1);
auto build = [&](auto build, int v, int l, int r) -> void{
if ( l == r ){
T[v].pb(a[l]);
} else{
int md = (l + r) >> 1;
build(build, v * 2, l, md);
build(build, v * 2 + 1, md + 1, r);
merge(all(T[v * 2]), all(T[v * 2 + 1]), back_inserter(T[v]));
}
};
build(build, 1, 0, n - 1);
}
void query(int v, int l, int r, int tl, int tr){
if ( l > tr or r < tl ){
return;
}
if ( tl <= l && tr >= r ){
auto &tmp = T[v];
int it = lower_bound(all(tmp), ar<int,2>{L_, -1}) - tmp.begin();
while ( it < tmp.size() && tmp[it][0] <= R_ ){
ans.pb(max(X - tmp[it][1], abs(tmp[it][0] - Y)));
it++;
} return;
}
int md = (l + r) >> 1;
query(v * 2, l, md, tl, tr);
query(v * 2 + 1, md + 1, r, tl, tr);
}
void query(int X_, int Y_, int L, int R, int l, int r){
if ( l > r ) return;
X = X_, Y = Y_, L_ = L, R_ = R;
query(1, 0, n - 1, l, r);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector <int> x(n), y(n);
for ( int i = 0; i < n; i++ ){
int a, b; cin >> a >> b;
x[i] = a + b;
y[i] = a - b;
}
{ // just sorting
vector <int> pp(n);
iota(all(pp), 0);
sort(all(pp), [&](int &u, int &v){
if ( x[u] == x[v] ){
return y[u] < y[v];
}
return x[u] < x[v];
});
auto xx_ = x, yy_ = y;
for ( int i = 0; i < n; i++ ){
x[i] = xx_[pp[i]];
y[i] = yy_[pp[i]];
}
}
vector <int> L(n);
auto ok = [&](int d){
vector <int> p_;
int j = 0;
for ( int i = 0; i < n; i++ ){
while ( x[i] - x[j] > d ) j++;
L[i] = j;
p_.pb(y[i]);
p_.pb(y[i] - d);
p_.pb(y[i] + d);
}
sort(all(p_));
p_.resize(unique(all(p_)) - p_.begin());
int s = p_.size();
auto get = [&](int x){
return lower_bound(all(p_), x) - p_.begin() + 1;
};
vector <vector<ar<int,3>>> qu(n);
for ( int i = 1; i < n; i++ ){
qu[i - 1].pb({1, get(y[i] - d), get(y[i] + d)});
if ( L[i] > 0 ){
qu[L[i] - 1].pb({0, get(y[i] - d), get(y[i] + d)});
}
}
int ans = 0;
Fenw fn(s);
for ( int i = 0; i < n; i++ ){
fn.upd(get(y[i]), 1);
for ( auto &[t, l, r]: qu[i] ){
if ( t > 0 ){
ans += fn.get(l, r);
} else{
ans -= fn.get(l, r);
}
}
}
return ans < k;
};
int l = 0, r = 1e10 + 5;
while ( l + 1 < r ){
int md = (l + r) >> 1;
if ( ok(md) ) l = md;
else r = md;
} ok(l);
vector <ar<int,2>> p(n);
for ( int i = 0; i < n; i++ ){
p[i] = {y[i], x[i]};
}
SegTree seg(p);
for ( int i = 0; i < n; i++ ){
seg.query(x[i], y[i], y[i] - l, y[i] + l, L[i], i - 1);
}
while ( ans.size() < k ){
ans.pb(l + 1);
}
sort(all(ans));
for ( auto &x: ans ){
cout << x << ln;
}
cout << '\n';
}
