#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
ll N, K, bit[750005];
pll p[250005];
void modify(int pos, int val)
{
for (int i = pos; i <= 3 * N; i += (i & -i))
bit[i] += val;
}
ll query(int pos)
{
ll val = 0;
for (int i = pos; i > 0; i -= (i & -i))
val += bit[i];
return val;
}
ll calc(ll L)
{
vector<tuple<ll, int, ll, ll>> v;
vector<ll> vy;
ll res = 0;
for (int i = 1; i <= N; i++)
{
ll x = p[i].F + p[i].S, y = p[i].F - p[i].S;
v.emplace_back(make_tuple(x - L, -1, y, 0));
v.emplace_back(make_tuple(x, 0, y - L, y + L));
v.emplace_back(make_tuple(x + L, 1, y, 0));
vy.emplace_back(y - L);
vy.emplace_back(y);
vy.emplace_back(y + L);
}
vy.emplace_back(-1e12);
sort(vy.begin(), vy.end());
vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
sort(v.begin(), v.end());
for (int i = 1; i <= 3 * N; i++)
bit[i] = 0;
for (auto [x, t, l, r] : v)
{
if (t == -1)
modify(lower_bound(vy.begin(), vy.end(), l) - vy.begin(), 1);
if (t == 1)
modify(lower_bound(vy.begin(), vy.end(), l) - vy.begin(), -1);
if (t == 0)
{
int L = lower_bound(vy.begin(), vy.end(), l) - vy.begin(), R = lower_bound(vy.begin(), vy.end(), r) - vy.begin();
res += query(R) - query(L - 1) - 1;
}
}
return res / 2;
}
signed main()
{
cin >> N >> K;
for (int i = 1; i <= N; i++)
cin >> p[i].F >> p[i].S;
ll L = 1, R = 4'000'000'000;
while (L < R)
{
ll mid = (L + R) / 2;
if (calc(mid) < K)
L = mid + 1;
else
R = mid;
}
L--;
vector<tuple<ll, int, ll, ll>> v;
multiset<ll> ans;
set<pll> st;
for (int i = 1; i <= N; i++)
{
ll x = p[i].F + p[i].S, y = p[i].F - p[i].S;
v.emplace_back(make_tuple(x - L, -i, y, 0));
v.emplace_back(make_tuple(x, i, y - L, y + L));
v.emplace_back(make_tuple(x + L, i + N, y, 0));
}
sort(v.begin(), v.end());
for (auto [x, t, l, r] : v)
{
if (t < 0)
st.insert(pll(l, -t));
else if (t > N)
st.erase(pll(l, t - N));
else
{
auto lter = st.lower_bound(pll(l, 0)), rter = st.upper_bound(pll(r, N + 1));
while(lter != rter)
{
ll i = lter->S;
if(i < t)
ans.insert(abs(p[t].F - p[i].F) + abs(p[t].S - p[i].S));
++lter;
}
}
}
while(ans.size() < K)
ans.insert(R);
for(ll i : ans)
cout << i << '\n';
}
