/// gpt's code, not me
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Point {
ll x, y;
ll u, v;
int id;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long K;
cin >> N >> K;
vector<Point> p(N);
for (int i = 0; i < N; i++) {
cin >> p[i].x >> p[i].y;
p[i].u = p[i].x + p[i].y;
p[i].v = p[i].x - p[i].y;
p[i].id = i;
}
sort(p.begin(), p.end(), [](auto &a, auto &b) {
if (a.u != b.u) return a.u < b.u;
return a.v < b.v;
});
// Min-heap of (distance, i, j)
priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<>> pq;
// Next pointer for each i
vector<int> nxt(N);
for (int i = 0; i < N; i++) {
if (i + 1 < N) {
ll dist = abs(p[i+1].x - p[i].x) + abs(p[i+1].y - p[i].y);
pq.push({dist, i, i+1});
nxt[i] = i + 1;
} else {
nxt[i] = -1;
}
}
vector<ll> ans;
ans.reserve(K);
while (!pq.empty() && (long long)ans.size() < K) {
auto [d, i, j] = pq.top();
pq.pop();
ans.push_back(d);
// Move j forward for same i
if (j + 1 < N) {
ll nd = abs(p[j+1].x - p[i].x) + abs(p[j+1].y - p[i].y);
pq.push({nd, i, j+1});
}
}
for (auto x : ans) {
cout << x << "\n";
}
return 0;
}
