#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int base = 1<<18; vector<int> T(2*base,0); void update(ll x, ll val) { x+=base; T[x]+=val; x/=2; while(x > 0) { T[x] = T[x+x] + T[x+x+1]; x/=2; } } ll query(ll a, ll b) { if(a>b) return 0; if(a==b) return T[a+base]; a+=base-1; b+=base+1; ll res = 0; while(a/2 != b/2) { if(a%2==0) res += T[a+1]; if(b%2==1) res += T[b-1]; a/=2; b/=2; } return res; } struct Point { ll x, y; friend bool operator<(Point a, Point b) { return a.y < b.y; } }; ll M = 250'010; vector<ll> cnt(M,1); ll n; ll inf = 1e18; vector<Point> pkt; vector<ll> X, Y; ll numer = 1; vector<ll> dists; ll count(ll d) { vector<pair<ll, ll>> sweep; for(int i=0; i<n; ++i) { sweep.push_back({pkt[i].y - d - 1, i}); sweep.push_back({pkt[i].y, i}); } ll sum = 0; sort(sweep.begin(), sweep.end()); for(auto[poz, i] : sweep) { if(pkt[i].y > poz) { int idx1 = lower_bound(X.begin(), X.end(), pkt[i].x-d) - X.begin(); int idx2 = upper_bound(X.begin(), X.end(), pkt[i].x+d) - X.begin() - 1; sum -= query(idx1, idx2); } else { int idx1 = lower_bound(X.begin(), X.end(), pkt[i].x-d) - X.begin(); int idx2 = upper_bound(X.begin(), X.end(), pkt[i].x+d) - X.begin() - 1; sum += query(idx1, idx2); update(lower_bound(X.begin(), X.end(), pkt[i].x) - X.begin(), 1); } } return sum; } ll calc_dist(ll i, ll j) { return max(abs(pkt[i].x-pkt[j].x), abs(pkt[i].y-pkt[j].y)); } vector<ll> get_dists(ll d) { vector<ll> dists; vector<pair<ll, ll>> sweep; for(int i=0; i<n; ++i) { sweep.push_back({pkt[i].y + d + 1, i}); sweep.push_back({pkt[i].y, i}); } set<pair<ll, ll>> iksy; sort(sweep.begin(), sweep.end()); for(auto[poz, i] : sweep) { if(pkt[i].y < poz) { iksy.erase({pkt[i].x, i}); } else { auto idx1 = iksy.lower_bound({pkt[i].x-d, 0}); auto idx2 = iksy.upper_bound({pkt[i].x+d, 1e9}); for(auto it=idx1; it!=idx2; ++it) { dists.push_back(calc_dist(i, it->second)); } iksy.insert({pkt[i].x, i}); } } return dists; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll k; cin >> n >> k; pkt.resize(n); for(ll i=0; i<n; ++i) { ll x,y; cin >> x >> y; pkt[i] = {x+y,x-y}; X.push_back(x+y); Y.push_back(x-y); } sort(X.begin(), X.end()); sort(pkt.begin(), pkt.end()); ll lo = 0; ll hi = 4e9; while(lo < hi) { ll mid = (lo+hi)/2; if(count(mid) < k) lo = mid+1; else hi = mid; } // cout << lo << "\n"; vector<ll> dists = get_dists(lo-1); sort(dists.begin(), dists.end()); while(dists.size() < k) dists.push_back(lo); for(int i=0; i<k; ++i) cout << dists[i] << "\n"; return 0; }