/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;
template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
int n, size, log;
vector<T> data;
vector<U> data_action;
F1 TT; // monoid operation (always adjacent)
T T_id; // monoid identity
F2 UU; // monoid operation (superset, subset)
U U_id; // monoid identity
F3 UT; // action of U on T (superset, subset)
// O(n)
segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
segment_tree_base &operator=(const segment_tree_base &seg){
n = seg.n;
size = seg.size;
log = seg.log;
data = seg.data;
data_action = seg.data_action;
}
// O(1)
friend void swap(segment_tree_base &x, segment_tree_base &y){
swap(x.n, y.n);
swap(x.size, y.size);
swap(x.log, y.log);
swap(x.data, y.data);
swap(x.data_action, y.data_action);
}
// O(n)
void build(int n){
assert(n >= 0);
this->n = n;
size = 1;
while(size < n) size <<= 1;
log = __lg(size);
ifQ data.assign(size << 1, T_id);
ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
}
// O(n)
void build(int n, T x){
static_assert(HAS_QUERY);
assert(n >= 0);
this->n = n;
size = 1;
while(size < n) size <<= 1;
log = __lg(size);
data.assign(size << 1, T_id);
fill(data.begin() + size, data.begin() + size + n, x);
for(auto i = size - 1; i >= 1; -- i) refresh(i);
ifU data_action.assign(size, U_id);
}
// O(n)
template<class V>
void build(const vector<V> &a){
static_assert(HAS_QUERY);
n = (int)a.size();
size = 1;
while(size < n) size <<= 1;
log = __lg(size);
data.assign(size << 1, T_id);
copy(a.begin(), a.end(), data.begin() + size);
for(auto i = size - 1; i >= 1; -- i) refresh(i);
ifU data_action.assign(size, U_id);
}
// O(n)
void build_action(int n){
static_assert(!HAS_QUERY && HAS_UPDATE);
assert(n >= 0);
build(n);
}
// O(n)
void build_action(int n, U f){
static_assert(!HAS_QUERY && HAS_UPDATE);
assert(n >= 0);
this->n = n;
size = 1;
while(size < n) size <<= 1;
log = __lg(size);
data_action.assign(size << 1, U_id);
fill(data_action.begin() + size, data_action.begin() + size + n, f);
}
// O(n)
template<class V>
void build_action(const vector<V> &a){
static_assert(!HAS_QUERY && HAS_UPDATE);
n = (int)a.size();
size = 1;
while(size < n) size <<= 1;
log = __lg(size);
data_action.assign(size << 1, U_id);
copy(a.begin(), a.end(), data_action.begin() + size);
}
// O(1)
void refresh(int u){
static_assert(HAS_QUERY);
data[u] = TT(data[u << 1], data[u << 1 | 1]);
}
// O(1)
void apply(int u, U f){
static_assert(HAS_UPDATE);
ifQ data[u] = UT(f, data[u]);
if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
}
// O(1)
void push(int u){
static_assert(HAS_UPDATE);
apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
data_action[u] = U_id;
}
// O(log(n)) if HAS_UPDATE, O(1) otherwise.
T query(int p){
static_assert(HAS_QUERY);
assert(0 <= p && p < n);
p += size;
ifU for(auto i = log; i >= 1; -- i) push(p >> i);
return data[p];
}
// O(log(n))
U query_action(int p){
static_assert(!HAS_QUERY && HAS_UPDATE);
assert(0 <= p && p < n);
p += size;
ifU for(auto i = log; i >= 1; -- i) push(p >> i);
return data_action[p];
}
// O(log(n))
T query(int ql, int qr){
static_assert(HAS_QUERY);
assert(0 <= ql && ql <= qr && qr <= n);
if(ql == qr) return T_id;
ql += size, qr += size;
ifU for(auto i = log; i >= 1; -- i){
if(ql >> i << i != ql) push(ql >> i);
if(qr >> i << i != qr) push(qr >> i);
}
T res_left = T_id, res_right = T_id;
for(; ql < qr; ql >>= 1, qr >>= 1){
if(ql & 1) res_left = TT(res_left, data[ql ++]);
if(qr & 1) res_right = TT(data[-- qr], res_right);
}
return TT(res_left, res_right);
}
// O(1)
T query_all() const{
static_assert(HAS_QUERY);
return data[1];
}
// O(n)
vector<T> to_array(){
static_assert(HAS_QUERY);
ifU for(auto u = 1; u < size; ++ u) push(u);
return vector<T>(data.begin() + size, data.begin() + size + n);
}
// O(n)
vector<U> to_array_of_updates(){
static_assert(!HAS_QUERY && HAS_UPDATE);
for(auto u = 1; u < size; ++ u) push(u);
return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
}
// O(log(n))
void set(int p, T x){
static_assert(HAS_QUERY);
assert(0 <= p && p < n);
p += size;
ifU for(auto i = log; i >= 1; -- i) push(p >> i);
data[p] = x;
for(auto i = 1; i <= log; ++ i) refresh(p >> i);
}
// O(log(n))
void set_action(int p, U f){
static_assert(!HAS_QUERY && HAS_UPDATE);
assert(0 <= p && p < n);
p += size;
for(auto i = log; i >= 1; -- i) push(p >> i);
data_action[p] = f;
}
// O(log(n))
void update(int p, U f){
static_assert(HAS_UPDATE);
assert(0 <= p && p < n);
p += size;
for(auto i = log; i >= 1; -- i) push(p >> i);
ifQ{
data[p] = UT(f, data[p]);
for(auto i = 1; i <= log; ++ i) refresh(p >> i);
}
else data_action[p] = UU(f, data_action[p]);
}
// O(log(n))
void update(int ql, int qr, U f){
static_assert(HAS_UPDATE);
assert(0 <= ql && ql <= qr && qr <= n);
if(ql == qr) return;
ql += size, qr += size;
for(auto i = log; i >= 1; -- i){
if(ql >> i << i != ql) push(ql >> i);
if(qr >> i << i != qr) push(qr >> i);
}
int _ql = ql, _qr = qr;
for(; ql < qr; ql >>= 1, qr >>= 1){
if(ql & 1) apply(ql ++, f);
if(qr & 1) apply(-- qr, f);
}
ql = _ql, qr = _qr;
ifQ for(auto i = 1; i <= log; ++ i){
if(ql >> i << i != ql) refresh(ql >> i);
if(qr >> i << i != qr) refresh(qr >> i);
}
}
void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
static_assert(HAS_QUERY && HAS_UPDATE);
assert(0 <= ql && ql <= qr && qr <= n);
if(ql == qr) return;
ql += size, qr += size;
for(auto i = log; i >= 1; -- i){
if(ql >> i << i != ql) push(ql >> i);
if(qr >> i << i != qr) push(qr >> i);
}
auto recurse = [&](auto self, int u)->void{
if(exit_rule(data[u])) return;
if(enter_rule(data[u])){
apply(u, update_rule(data[u]));
return;
}
push(u);
self(self, u << 1), self(self, u << 1 | 1);
refresh(u);
};
int _ql = ql, _qr = qr;
for(; ql < qr; ql >>= 1, qr >>= 1){
if(ql & 1) recurse(recurse, ql ++);
if(qr & 1) recurse(recurse, -- qr);
}
ql = _ql, qr = _qr;
for(auto i = 1; i <= log; ++ i){
if(ql >> i << i != ql) refresh(ql >> i);
if(qr >> i << i != qr) refresh(qr >> i);
}
}
// pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
// Returns max r with T
// O(log(n))
int max_pref(int ql, auto pred){
static_assert(HAS_QUERY);
assert(0 <= ql && ql <= n && pred(T_id));
if(ql == n) return n;
ql += size;
ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
T sum = T_id;
do{
while(~ql & 1) ql >>= 1;
if(!pred(TT(sum, data[ql]))){
while(ql < size){
ifU push(ql);
ql = ql << 1;
if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
}
return ql - size;
}
sum = TT(sum, data[ql]);
++ ql;
}while((ql & -ql) != ql);
return n;
}
// pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
// Returns min l with T
// O(log(n))
int min_suff(int qr, auto pred){
static_assert(HAS_QUERY);
assert(0 <= qr && qr <= n && pred(T_id));
if(qr == 0) return 0;
qr += size;
ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
T sum = T_id;
do{
-- qr;
while(qr > 1 && qr & 1) qr >>= 1;
if(!pred(TT(data[qr], sum))){
while(qr < size){
ifU push(qr);
qr = qr << 1 | 1;
if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
}
return qr + 1 - size;
}
sum = TT(data[qr], sum);
}while((qr & -qr) != qr);
return 0;
}
template<class output_stream>
friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
out << "{";
for(auto i = 0; i < seg.n; ++ i){
ifQ out << seg.query(i);
else out << seg.query_action(i);
if(i != seg.n - 1) out << ", ";
}
return out << '}';
}
#undef ifQ
#undef ifU
};
// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
using U = int;
auto _UU = [&](U, U)->U{ return U{}; };
auto _UT = [&](U, T)->T{ return T{}; };
return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
using T = int;
auto _TT = [&](T, T)->T{ return T{}; };
auto _UT = [&](U, T)->T{ return T{}; };
return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> comp_num;
vector<pair<int, int>> vec;
vector<pair<array<int, 2>, int>> pre_needed;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
vec.emplace_back(x + y, x - y);
pre_needed.push_back({{x + y, x - y}, 1});
comp_num.emplace_back(x - y);
}
sort(all(vec));
sort(all(comp_num));
comp_num.erase(unique(comp_num.begin(), comp_num.end()), comp_num.end());
auto op = [&](int a, int b) -> int { return a + b; };
auto st = make_Q_segment_tree(op, 0);
st.build(isz(comp_num));
auto getge = [&](int val) -> int {
return lower_bound(all(comp_num), val) - comp_num.begin();
};
auto query = [&](int val) {
int res = 0;
int ptr = 0, ptr2 = 0;
for (int i = 0; i < n; ++i) {
while (ptr2 < n and vec[i].first - vec[ptr2].first > val) {
int pos = getge(vec[ptr2].second);
st.set(pos, st.query(pos) - 1);
++ptr2;
}
while (ptr < n and vec[ptr].first <= vec[i].first + val) {
int pos = getge(vec[ptr].second);
st.set(pos, st.query(pos) + 1);
++ptr;
}
int l = getge(vec[i].second - val);
int r = getge(vec[i].second + val + 1);
res += st.query(l, r) - 1;
}
while (ptr2 < n) {
int pos = getge(vec[ptr2].second);
st.set(pos, st.query(pos) - 1);
++ptr2;
}
return res / 2;
};
int l = 0, r = 4e9;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid) >= k) r = mid;
else l = mid + 1;
}
auto dis = [&](const auto &A, const auto &B) -> int {
return max(abs(A.first - B.second), abs(A.second - B.first));
};
int lim = l - 1;
int ptr = 0, ptr2 = 0;
map<int, int> mp;
set<pair<int, int>> s;
for (int i = 0; i < n; ++i) {
while (ptr2 < n and vec[i].first - vec[ptr2].first > lim) {
auto val = vec[ptr2];
swap(val.first, val.second);
s.erase(val);
++ptr2;
}
while (ptr < n and vec[ptr].first <= vec[i].first + lim) {
auto val = vec[ptr];
swap(val.first, val.second);
s.insert(val);
++ptr;
}
for (auto it = s.lower_bound(pair<int, int>{vec[i].second - lim, LLONG_MIN}); it != s.end() and it->first <= vec[i].second + lim; it = next(it)) {
mp[dis(vec[i], *it)]++;
}
}
for (auto [val, cnt] : mp) if (val) {
assert(cnt % 2 == 0);
k -= cnt / 2;
for (int i = 0; i < cnt / 2; ++i) cout << val << "\n";
}
for (int i = 0; i < k; ++i) cout << l << "\n";
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
cout << "Check array size pls sir" << endl;
#endif
}
