#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(x) (int)x.size()
#define f first
#define s second
/*
Date: 2022/06/10
Problem Link: https://oj.uz/problem/view/JOI21_road_construction
Topic(s): Binary search, sorting
Time Spent:
Solution Outline:
- The distance between two points can be written as max(abs((xi + yi) - (xj + yj)), abs((xi - yi) - (xj - yj)))
Binary search on v, which is the kth largest value. We have to check whether there more or less than k roads with
cost <= v.
- Maintain a sliding window of size v.
- Sort the points by xi + yi. For a point i, remove all points j that has xj + yj further than v units away.
- Put xi - yi into the set.
- We know all js that came before i must have xi + yi - (xj + yj) <= v. So we can simply call lower_bound on the set
with xi - yi - v and vi - vi + v. The range that it gives us will be the amount of points within v distance of i.
*/
const int MAXN = 2e5+5;
int n, k;
vector<pll> arr;
vector<ll> res;
ll sum(const pll& a){
return a.f + a.s;
}
ll dif(const pll& a){
return a.f - a.s;
}
bool check(ll v, bool upd){
int l = 0;
auto cmp = [](const pll& a, const pll& b){
if (dif(a) == dif(b)){
return a < b;
}else{
return a.f - a.s < b.f - b.s;
}
};
set<pll, decltype(cmp)> set(cmp);
ll ans = 0;
for (int i=0; i<n; i++){
while (l < n && sum(arr[i]) - sum(arr[l]) > v){
set.erase(arr[l]);
l++;
}
auto inc = set.lower_bound(arr[i]);
auto dec = inc;
while (inc != set.end() && dif(*inc) - dif(arr[i]) <= v){
if (upd) res.push_back(abs(arr[i].f - (*inc).f) + abs(arr[i].s - (*inc).s));
inc++;
ans++;
if (!upd && ans >=k){
return true;
}
}
while (dec != set.begin() && dif(arr[i]) - dif(*prev(dec)) <= v){
dec--;
if (upd) res.push_back(abs(arr[i].f - (*dec).f) + abs(arr[i].s - (*dec).s));
ans++;
if (!upd && ans >=k){
return true;
}
}
set.insert(arr[i]);
}
return ans >= k;
}
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> k;
arr.resize(n);
for (int i=0; i<n; i++){
int x, y;
cin >> x >> y;
arr[i] = {x, y};
}
sort(arr.begin(), arr.end(), [](const pll& a, const pll& b){
return a.f + a.s < b.f + b.s;
});
ll low = 0, high = 4e9;
while (low < high){
ll mid = (low + high)/2;
if (check(mid, false)){
high = mid;
}else{
low = mid+1;
}
}
check(low, true);
assert((int)res.size() >= k);
sort(res.begin(), res.end());
for (int i=0; i<k; i++){
cout << res[i] << "\n";
}
}
