#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 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); } add(lower_bound(all(ys), al[i].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; } 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; } 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 + l) { r++; al1.insert({lower_bound(all(ys), al[r].second) - ys.begin(), r}); } al1.erase({lower_bound(all(ys), al[i].second) - ys.begin(), i}); vector<pair<ll, ll>> rem; ll ind1 = lower_bound(all(ys), al[i].second - l) - ys.begin(); ll ind2 = upper_bound(all(ys), al[i].second + l) - 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); ll x1 = (al[x].first + al[x].second) / 2; ll y1 = (al[x].second - al[x].first) / 2; ll x2 = (al[i].first + al[i].second) / 2; ll y2 = (al[i].second - al[i].first) / 2; dis.push_back(abs(x1 - x2) + abs(y1 - y2)); } for (auto x : rem) al1.insert(x); } sort(all(dis)); while (dis.size() < k) dis.push_back(l + 1); for (ll x : dis) cout << x << "\n"; } int main() { sui; ll tc = 1; //cin >> tc; for (ll t = 1; t <= tc; t++) { solve(); } }