#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
x += k;
x %= mod;
if (x < 0)
x += mod;
}
void del(int &x, int k)
{
x -= k;
x %= mod;
if (x < 0)
x += mod;
}
template <class T>
struct Fenwick_Tree
{
vector<T> bit_add, bit_sub;
int n;
Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}
void clear()
{
fill(bit_add.begin(), bit_add.end(), T(0));
fill(bit_sub.begin(), bit_sub.end(), T(0));
}
void update(int u, int v, T val)
{
for (int i = u; i <= n; i += i & -i)
{
bit_add[i] += val;
bit_sub[i] += 1LL * (u - 1) * val;
}
for (int i = v; i <= n; i += i & -i)
{
bit_add[i] -= val;
bit_sub[i] -= 1LL * v * val;
}
}
void update(int u, T val) { update(u, u, val); }
T get(int u)
{
T ans1 = 0, ans2 = 0;
for (int i = u; i; i -= i & -i)
{
ans1 += bit_add[i];
ans2 += bit_sub[i];
}
return u * ans1 - ans2;
}
T get(int l, int r) { return get(r) - get(l - 1); }
};
pii a[maxn];
vi up[maxn];
vector<array<int, 3>> range[maxn];
vi nen1, nen2;
int n, k;
bool check(int d)
{
fo(i, 0, n) range[i].clear();
Fenwick_Tree<int> t(n + 5);
fo(i, 1, n)
{
int lx = lower_bound(all(nen1), a[i].fi - d) - nen1.begin() + 1;
int rx = upper_bound(all(nen1), a[i].fi + d) - nen1.begin();
int ly = lower_bound(all(nen2), a[i].se - d) - nen2.begin() + 1;
int ry = upper_bound(all(nen2), a[i].se + d) - nen2.begin();
range[lx - 1].push_back({ly, ry, -1});
range[rx].push_back({ly, ry, 1});
}
int ans = 0;
fo(i, 1, n)
{
for (int it : up[i])
t.update(it, 1);
for (auto [l, r, val] : range[i])
ans += val * t.get(l, r);
}
return ans - n >= 2 * k;
}
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
fo(i, 1, n)
{
int x, y;
cin >> x >> y;
a[i] = {x - y, x + y};
nen1.pb(a[i].fi);
nen2.pb(a[i].se);
}
sort(all(nen1));
sort(all(nen2));
nen1.erase(unique(all(nen1)), nen1.end());
nen2.erase(unique(all(nen2)), nen2.end());
fo(i, 1, n)
{
int x = lower_bound(all(nen1), a[i].fi) - nen1.begin() + 1;
int y = lower_bound(all(nen2), a[i].se) - nen2.begin() + 1;
up[x].pb(y);
}
// cout << check(1);en;
int l = 1, r = 4e9, ans = 4e9;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
// cout << ans <<"x";en;
sort(a + 1, a + n + 1);
vi v;
set<pii> st;
fo(i, 1, n)
{
pii now = {a[i].se - ans - 1, inf};
while (1)
{
auto it = st.upper_bound(now);
if (it == st.end() or it->fi > a[i].se + ans)
break;
if (it->se < a[i].fi - ans)
{
st.erase(it);
continue;
}
v.pb(max(abs(a[i].se - it->fi), abs(a[i].fi - it->se)));
now = *it;
}
st.insert({a[i].se, a[i].fi});
}
sort(all(v));
fo(i, 0, k - 1) cout << v[i] << "\n";
}
