#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const ll MAX_N = 2.5e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const ll LOG = 30;
ll n, k;
pair<ll, ll> al[MAX_N];
vector<ll> xs;
vector<ll> ys;
ll fen[MAX_N];
void add(ll x, ll y)
{
x++;
for (ll i = x; i < MAX_N; i += i & (-i)) fen[i] += y;
}
ll get(ll x)
{
x++;
ll ans = 0;
for (ll i = x; i > 0; i -= i & (-i)) ans += fen[i];
return ans;
}
ll check(ll x)
{
fill(fen, fen + n + 1, 0);
ll l = -1;
ll r = -1;
ll sum = 0;
for (ll i = 0; i < n; i++)
{
while (r + 1 < n && al[r + 1].first <= al[i].first + x)
{
r++;
add(lower_bound(all(ys), al[r].second) - ys.begin(), 1);
}
while (al[l + 1].first < al[i].first - x)
{
l++;
add(lower_bound(all(ys), al[l].second) - ys.begin(), -1);
}
sum += get(upper_bound(all(ys), al[i].second + x) - ys.begin() - 1) - get(lower_bound(all(ys), al[i].first - x) - ys.begin() - 1);
}
return (sum - n) / 2;
}
void solve() {
cin >> n >> k;
for (ll i = 0; i < n; i++)
{
cin >> al[i].first >> al[i].second;
al[i].first = al[i].first - al[i].second;
al[i].second = al[i].first + 2 * al[i].second;
xs.push_back(al[i].first);
ys.push_back(al[i].second);
}
sort(all(xs));
sort(all(ys));
xs.resize(unique(all(xs)) - xs.begin());
ys.resize(unique(all(ys)) - ys.begin());
sort(al, al + n);
ll l = 0;
ll r = 2e9;
while (r - l > 1)
{
ll mid1 = ((ll) r + l) >> 1;
if (check(mid1) < k) l = mid1;
else r = mid1;
}
ll num = l;
l = -1;
r = -1;
set<pair<ll, ll>> al1;
vector<ll> dis;
for (ll i = 0; i < n; i++)
{
while (r + 1 < n && al[r + 1].first <= al[i].first + num)
{
r++;
al1.insert({lower_bound(all(ys), al[r].second) - ys.begin(), r});
}
while (al[l + 1].first < al[i].first - num)
{
l++;
al1.erase({lower_bound(all(ys), al[l].second) - ys.begin(), l});
}
vector<pair<ll, ll>> rem;
ll ind1 = lower_bound(all(ys), al[i].second - num) - ys.begin();
ll ind2 = upper_bound(all(ys), al[i].second + num) - ys.begin();
while (al1.size())
{
auto ind = al1.lower_bound({ind1, -1});
if (ind == al1.end() || (*ind).first >= ind2) break;
ll x = (*ind).second;
rem.push_back(*ind);
al1.erase(ind);
if (x ^ i) dis.push_back(max(abs(al[x].first - al[i].first), abs(al[x].second - al[i].second)));
}
for (auto x : rem) al1.insert(x);
}
vector<ll> ans;
sort(all(dis));
for (ll i = 0; i < dis.size(); i += 2) ans.push_back(dis[i]);
while (ans.size() < k) ans.push_back(num + 1);
for (ll x : ans) cout << x << "\n";
}
ll main() {
sui;
ll tc = 1;
//cin >> tc;
for (ll t = 1; t <= tc; t++) {
solve();
}
}
