#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 250007;
const ll oo = 1e18;
struct BIT {
vi bit;
int n;
BIT(int _n) {
n = _n;
bit.resize(n);
}
void add(int pos, int val) {
assert(pos > 0);
for(; pos < n; pos += pos & -pos)
bit[pos] += val;
}
int qry(int pos) {
int res = 0;
for(; pos; pos -= pos & -pos)
res += bit[pos];
return res;
}
};
pair<ll, int> t[N * 4];
int n;
void upd(int pos, pair<ll, int> val, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1) {
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos < tm)
upd(pos, val, v * 2, tl, tm);
else
upd(pos, val, v * 2 + 1, tm, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
pair<ll, int> qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) / 2;
pair<ll, int> res = {-oo, -INF};
if(l < tm) res = max(res, qry(l, r, v * 2, tl, tm));
if(r > tm) res = max(res, qry(l, r, v * 2 + 1, tm, tr));
return res;
}
signed main()
{
IO_OP;
memset(t, 0xc0, sizeof t);
int k;
cin >> n >> k;
V<ll> x(n), y(n), X(n), Y(n);
V<array<ll, 3>> aux;
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
X[i] = x[i] + y[i], Y[i] = x[i] - y[i];
aux.PB({X[i], Y[i], i});
}
sort(ALL(aux));
V<ll> hebe = Y;
sort(ALL(hebe)), hebe.resize(unique(ALL(hebe)) - hebe.begin());
auto cnt_pairs = [&] (ll m) { // count the number of pairs with distance <= m
ll ans = 0;
V<array<ll, 4>> ev;
for(int i = 0; i < n; i++) {
ev.PB({X[i] + m, Y[i] - m, Y[i] + m, 1});
ev.PB({X[i] - m - 1, Y[i] - m, Y[i] + m, -1});
}
sort(ALL(ev));
BIT bit(n + 1);
int i = 0;
for(auto [x_val, l, r, op]:ev) {
while(i < SZ(aux) && aux[i][0] <= x_val) {
int tt = lower_bound(ALL(hebe), aux[i++][1]) - hebe.begin() + 1;
bit.add(tt, 1);
}
auto qry_less = [&] (ll val) {
int tt = lower_bound(ALL(hebe), val) - hebe.begin();
return bit.qry(tt);
};
ans += op * (qry_less(r + 1) - qry_less(l));
}
ans -= n;
assert(ans % 2 == 0);
ans /= 2;
return ans;
};
ll lb = 0, rb = 4e9 + 7;
while(lb <= rb) {
ll mb = (lb + rb) / 2;
if(cnt_pairs(mb) >= k) {
rb = mb - 1;
} else {
lb = mb + 1;
}
}
auto get_all = [&] (ll m) {
V<ll> res;
V<array<ll, 3>> ev;
V<pair<ll, int>> aux2;
for(int i = 0; i < n; i++) {
ev.PB({X[i] + m + 1, i, -1});
ev.PB({X[i] - m, i, 1});
aux2.EB(Y[i] - m, i);
}
sort(ALL(ev));
sort(ALL(aux2));
vi pos(n);
for(int i = 0; i < n; i++)
pos[aux2[i].S] = i;
auto activate = [&] (int i) {
upd(pos[i], {Y[i] + m, i});
};
auto deactivate = [&] (int i) {
upd(pos[i], {-oo, -INF});
};
int i = 0;
for(auto[x_val, y_val, _]:aux) {
while(i < SZ(ev) && ev[i][0] <= x_val) {
if(ev[i][2] == 1) {
activate(ev[i][1]);
} else {
deactivate(ev[i][1]);
}
i++;
}
vi todo;
while(true) {
int j = upper_bound(ALL(aux2), MP(y_val, INF)) - aux2.begin();
if(j == 0) break;
auto[mx, k] = qry(0, j);
if(mx >= y_val) {
deactivate(k);
todo.PB(k);
if(k < _)
res.PB(abs(x[k] - x[_]) + abs(y[k] - y[_]));
} else {
break;
}
}
for(int k:todo)
activate(k);
}
return res;
};
V<ll> ans = get_all(rb);
sort(ALL(ans)), assert(SZ(ans) < k);
while(SZ(ans) < k)
ans.PB(rb + 1);
for(ll i:ans)
cout << i << '\n';
}
