#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
int dist (pair<int, int> a, pair<int, int> b) {
return abs(a.f-b.f)+abs(a.s-b.s);
}
signed main (signed argc, char **argv) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> vt(n);
for (auto &i: vt) cin >> i.f >> i.s;
sort(vt.begin(), vt.end());
int len = 0;
for (int bt = 40; bt--;) {
int m = len+(1ll<<bt);
int cnt = 0;
set<pair<int, int>> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int upto = 0;
for (auto i: vt) {
while (pq.size() && pq.top().f < i.f-m) {
st.erase({vt[pq.top().s].s, pq.top().f});
pq.pop();
}
for (auto j = st.lower_bound({i.s-m, 0}); cnt < k && j != st.upper_bound({i.s+m, n}); ++j)
cnt += dist(i, vt[(*j).s]) <= m;
if (cnt >= k) break;
st.insert({i.s, upto});
pq.push({i.f, upto++});
}
if (cnt < k) len = m;
}
vector<int> ans;
set<pair<int, int>> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int upto = 0;
for (auto i: vt) {
while (pq.size() && pq.top().f < i.f-len) {
st.erase({vt[pq.top().s].s, pq.top().f});
pq.pop();
}
for (auto j = st.lower_bound({i.s-len, 0}); j != st.upper_bound({i.s+len, n}); ++j)
if (dist(i, vt[(*j).s]) <= len) ans.push_back(dist(i, vt[(*j).s]));
st.insert({i.s, upto});
pq.push({i.f, upto++});
}
int left = k-(int)ans.size();
sort(ans.begin(), ans.end());
for (int i: ans) cout << i << "\n";
while (left--) cout << len+1 << "\n";
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┗━┓ ┏━┛ + +
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the llama protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
//thanks cindy
