#include <bits/stdc++.h>
#define ent '\n'
#define int long long
using namespace std;
const int maxn = 250'012;
set<pair<int, int>> s[maxn * 4];
int x[maxn], y[maxn];
vector<pair<int, int>> ans;
int n, k;
struct slow_tree {
void upd(int v, int tl, int tr, int pos, int y) {
s[v].insert({y, pos});
if(tl == tr) {
return;
}
int mid = (tl + tr) >> 1;
if(pos <= mid) {
upd(v * 2, tl, mid, pos, y);
}
else {
upd(v * 2 + 1, mid + 1, tr, pos, y);
}
}
void add(int v, int tl, int tr, int lx, int rx, int ly, int ry, int i) {
if(tl > rx || lx > tr) return;
if(tl >= lx && tr <= rx) {
pair<int, int> cur = {ly, 0};
while((int)ans.size() <= k) {
auto it = s[v].upper_bound(cur);
if(it == s[v].end() || it -> first > ry) return;
ans.push_back({i, it -> second});
cur = *it;
}
return;
}
int mid = (tl + tr) >> 1;
add(v * 2, tl, mid, lx, rx, ly, ry, i);
add(v * 2 + 1, mid + 1, tr, lx, rx, ly, ry, i);
}
bool check(int d) {
for(int i = 1; i <= n * 4; i++) {
s[i].clear();
}
ans.clear();
for(int i = 1; i <= n; i++) {
int pos = i;
for(int l = 1, r = i - 1; l <= r;) {
int mid = (l + r) >> 1;
if(x[i] - x[mid] <= d) {
pos = mid;
r = mid - 1;
}
else l = mid + 1;
}
add(1, 1, n, pos, i, y[i] - d, y[i] + d, i);
upd(1, 1, n, i, y[i]);
if(ans.size() >= k) return true;
}
return ans.size() >= k;
}
} ft;
struct fenwick {
vector<int32_t> t;
fenwick() {
t.clear();
}
void resize(int n) {
t = vector<int32_t> (n, 0);
}
void clear() {
for(int32_t i = 0; i < t.size(); i++) {
t[i] = 0;
}
}
void upd(int32_t i, int32_t x) {
for(; i < t.size(); i |= (i + 1)) {
t[i] += x;
}
}
int32_t get(int32_t i) {
int32_t ans = 0;
for(; i >= 0; i = (i & (i + 1)) - 1) {
ans += t[i];
}
return ans;
}
} t[maxn * 4];
vector<int32_t> g[maxn * 4];
void build(int v, int tl, int tr) {
for(int i = tl; i <= tr; i++) {
g[v].push_back(y[i]);
}
sort(g[v].begin(), g[v].end());
g[v].resize(unique(g[v].begin(), g[v].end()) - g[v].begin());
t[v].resize((int)g[v].size());
if(tl == tr) return;
int mid = (tl + tr) >> 1;
build(v * 2, tl, mid);
build(v * 2 + 1, mid + 1, tr);
}
void upd(int v, int tl, int tr, int pos, int y) {
t[v].upd(lower_bound(g[v].begin(), g[v].end(), y) - g[v].begin(), 1);
if(tl == tr) return;
int mid = (tl + tr) >> 1;
if(pos <= mid) {
upd(v * 2, tl, mid, pos, y);
}
else {
upd(v * 2 + 1, mid + 1, tr, pos, y);
}
}
int get(int v, int tl, int tr, int l, int r, int ly, int ry) {
if(tl > r || l > tr) return 0;
if(tl >= l && tr <= r) {
return t[v].get((int32_t)(upper_bound(g[v].begin(), g[v].end(), ry) - g[v].begin()) - 1) - t[v].get((int32_t)(lower_bound(g[v].begin(), g[v].end(), ly) - g[v].begin()) - 1);
}
int mid = (tl + tr) >> 1;
return get(v * 2, tl, mid, l, r, ly, ry) + get(v * 2 + 1, mid + 1, tr, l, r, ly, ry);
}
bool check(int d) {
for(int i = 1; i <= n * 4; i++) {
t[i].clear();
}
int val = 0;
for(int i = 1; i <= n; i++) {
int pos = i;
for(int l = 1, r = i - 1; l <= r;) {
int mid = (l + r) >> 1;
if(x[i] - x[mid] <= d) {
pos = mid;
r = mid - 1;
}
else l = mid + 1;
}
val += get(1, 1, n, pos, n, y[i] - d, y[i] + d);
upd(1, 1, n, i, y[i]);
if(val >= k) return true;
}
return val >= k;
}
void solve() {
cin >> n >> k;
vector<pair<int, int>> cur;
for(int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
x[i] += y[i];
y[i] = x[i] - 2 * y[i];
cur.push_back({x[i], y[i]});
}
sort(cur.begin(), cur.end());
for(int i = 1; i <= n; i++) {
x[i] = cur[i - 1].first, y[i] = cur[i - 1].second;
}
build(1, 1, n);
int val = -1;
for(int l = 0, r = 4e9; l <= r;) {
int mid = (l + r) >> 1;
if(check(mid)) {
val = mid;
r = mid - 1;
}
else l = mid + 1;
}
vector<int> v;
ft.check(val - 1);
for(auto [i, j] : ans) {
v.push_back(max(abs(x[i] - x[j]), abs(y[i] - y[j])));
}
sort(v.begin(), v.end());
while(v.size() < k) {
v.push_back(val);
}
for(int x : v) {
cout << x << ent;
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
