#include <bits/stdc++.h> #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; #define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false) #define all(a) a.begin(), a.end() #define F first #define S second #define ll long long #define pii pair<ll, ll> #define ppp pair<ll, pii> #define dout cout << fixed << setprecision(15) #define mid ((l + r) / 2) #define lc (2 * id) #define rc (lc + 1) const ll maxn = 3e5 + 10, maxm = 3e3 + 10, oo = 4e9 + 10, lg = 31, sq = 1400, mod = 998244353; int n, k; vector<ll> cmp; vector<int> v[maxn]; pii a[maxn]; ppp b[maxn]; int fen[maxn]; int id(ll x){ return lower_bound(all(cmp), x) - cmp.begin(); } void add(int i, int val){ for (; i <= n; i += i & -i) fen[i] += val; } int get(int i){ int res = 0; for (; i > 0; i -= i & -i) res += fen[i]; return res; } ll check(ll x){ int j = 1; ll res = 0; for (int i = 1; i <= n; i++) fen[i] = 0; for (int i = 1; i <= n; i++) { while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > x) { add(id(a[j].S - a[j].F), -1); j++; } res += get(id(a[i].S - a[i].F + x + 1) - 1) - get(id(a[i].S - a[i].F - x) - 1); add(id(a[i].S - a[i].F), 1); } return res; } int p[2][maxn]; void solve() { cin >> n >> k; for (int i = 1; i <= n;i++) cin >> a[i].F >> a[i].S; for (int i = 1; i <= n;i++) b[i] = {a[i].F + a[i].S, a[i]}; sort(b + 1, b + n + 1); for (int i = 1; i <= n;i++) a[i] = b[i].S; for (int i = 1; i <= n;i++) cmp.push_back(a[i].S - a[i].F); cmp.push_back(-oo); sort(all(cmp)); cmp.resize(unique(all(cmp)) - cmp.begin()); for (int i = 1; i <= n;i++) v[id(a[i].S - a[i].F)].push_back(i); ll l = 1, r = mod; while(r - l > 1) if(check(mid) >= k) r = mid; else l = mid; vector<ll> ans; for (int i = 1; i <= k - check(l);i++) ans.push_back(r); int j = 1; for (int i = 1; i <= n; i++) { while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l) { p[0][id(a[j].S - a[j].F)]++; j++; } for (int o = id(a[i].S - a[i].F - l); o <= id(a[i].S - a[i].F + l + 1) - 1; o++) for (int ii = p[0][o]; ii < p[1][o];ii++) ans.push_back(1ll * abs(a[i].F - a[v[o][ii]].F) + abs(a[i].S - a[v[o][ii]].S)); p[1][id(a[i].S - a[i].F)]++; } sort(all(ans)); for(auto i : ans) cout << i << "\n"; } signed main() { threesum; int t = 1; //cin >> t; while(t--) solve(); }