#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e5 + 15;
const int INF = 2e9 + 1;
struct node {
node *l, *r;
pair<int, int> mn;
node(node *l_, node *r_, pair<int, int> mn_) : l(l_), r(r_), mn(mn_) {}
};
node *copy(node *t) {
return new node(t->l, t->r, t->mn);
}
node *build(int tl, int tr) {
if (tr - tl == 1) {
return new node(0, 0, {INF, INF});
}
int tm = (tl + tr) / 2;
return new node(build(tl, tm), build(tm, tr), {INF, INF});
}
pair<int, int> get(node *t, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l) {
return {INF, INF};
}
if (tl >= l && tr <= r) {
return t->mn;
}
int tm = (tl + tr) / 2;
return min(get(t->l, tl, tm, l, r), get(t->r, tm, tr, l, r));
}
void update(node *&t, int tl, int tr, int pos, pair<int, int> mn) {
t = copy(t);
if (tr - tl == 1) {
t->mn = mn;
return;
}
int tm = (tl + tr) / 2;
if (pos < tm) {
update(t->l, tl, tm, pos, mn);
} else {
update(t->r, tm, tr, pos, mn);
}
t->mn = min(t->l->mn, t->r->mn);
}
int n, k;
int x[N], y[N];
vector<pair<long long, pair<int, int>>> D;
node *t[N];
int ordx[N], ordy[N];
int posx[N], posy[N];
int ry[N];
void go(int fx, int fy) {
// cout << "--- " << fx << " " << fy << " ---\n";
iota(ordx, ordx + n, 0);
iota(ordy, ordy + n, 0);
sort(ordx, ordx + n, [&](int i, int j) {
return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]) || (x[i] == x[j] && y[i] == y[j] && i < j);
});
sort(ordy, ordy + n, [&](int i, int j) {
return y[i] < y[j] || (y[i] == y[j] && x[i] < x[j]) || (y[i] == y[j] && x[i] == x[j] && i < j);
});
for (int i = 0; i < n; ++i) {
posx[ordx[i]] = i;
posy[ordy[i]] = i;
}
node *cur = build(0, n);
for (int i = 0, j = 0; i < n; ++i) {
while (x[ordx[j]] <= x[ordx[i]] - fx && j < i) {
int id = ordx[j];
update(cur, 0, n, posy[id], {-x[id] - y[id], posy[id]});
++j;
}
t[ordx[i]] = cur;
}
for (int i = 0, j = 0; i < n; ++i) {
while (y[ordy[j]] <= y[ordy[i]] - fy && j < i) {
++j;
}
ry[ordy[i]] = j;
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
for (int i = 0; i < n; ++i) {
auto mn = get(t[i], 0, n, 0, ry[i]);
if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
}
for (int _ = 0; _ < k && !q.empty(); ++_) {
int i = q.top().second;
q.pop();
auto mn = get(t[i], 0, n, 0, ry[i]);
D.push_back({(long long)mn.first + x[i] + y[i], {min(i, ordy[mn.second]), max(i, ordy[mn.second])}});
update(t[i], 0, n, mn.second, {INF, INF});
mn = get(t[i], 0, n, 0, ry[i]);
if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
}
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
go(0, 0);
for (int i = 0; i < n; ++i) {
x[i] *= -1;
}
go(1, 0);
sort(D.begin(), D.end());
D.resize(unique(D.begin(), D.end()) - D.begin());
D.resize(k);
for (int i = 0; i < k; ++i) {
cout << D[i].first << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
