#define taskname "" #include <bits/stdc++.h> using namespace std; const long long kMaxDist = 4000000000; const long long kInf = 5000000000000000000; int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<pair<long long, long long>> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i].first >> a[i].second; a[i] = {a[i].first + a[i].second, a[i].first - a[i].second}; } sort(a.begin() + 1, a.end()); auto f = [&](long long d) -> pair<long long, vector<long long>> { set<pair<long long, long>> s; queue<pair<long long, long long>> q; vector<long long> v; int c = 0; for (int i = 1; i <= n; i++) { while (!q.empty() && q.front().first < a[i].first - d) { s.erase({q.front().second, q.front().first}); q.pop(); } auto it = s.lower_bound({a[i].second - d, -kInf}); while (it != s.end() && it->first <= a[i].second + d) { c++; v.push_back(max(abs(a[i].second - it->first), a[i].first - it->second)); if (c >= k) { break; } it++; } if (c >= k) { break; } s.insert({a[i].second, a[i].first}); q.push({a[i].first, a[i].second}); } return {c, v}; }; long long low = 1, high = kMaxDist, x; while (low <= high) { long long mid = (low + high) / 2; pair<long long, vector<long long>> b = f(mid); if (b.first >= k) { x = mid; high = mid - 1; } else { low = mid + 1; } } vector<long long> e = f(x - 1).second; sort(e.begin(), e.end()); for (auto i : e) { cout << i << '\n'; } for (int i = 1; i <= k - e.size(); i++) { cout << x << '\n'; } return 0; }

road_construction.cpp: In function 'int main()':
road_construction.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~