#include <bits/stdc++.h>
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#define int int64_t
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0, x, y; i < n; ++i) {
cin >> x >> y;
a[i] = x;
}
sort(a.begin(), a.end());
// for each i, store l[i], r[i], initially both equal to i-1 and i+1 respectively
// we use a top priority queue to do this, skipping pairs when they've already been counted.
// once we use pair at i, if we were left, do left--
// or we can just push {dist, (i, left)} or {dist, (i, right)} instead and then push the next thing as needed
// maintain set of used
set<pair<int, int>> used;
min_heap<pair<int, pair<int, int>>> pq;
for (int i = 0; i < n; ++i) {
if (i != 0) {
pq.push({a[i] - a[i - 1], {i, i - 1}});
}
if (i != n - 1) {
pq.push({a[i + 1] - a[i], {i, i + 1}});
}
}
while (k) {
int d = pq.top().first;
auto [i, wh] = pq.top().second;
pq.pop();
if (used.contains({i, wh})) {
continue;
}
used.insert({i, wh});
used.insert({wh, i});
cout << d << '\n';
k--;
if (wh < i) {
if (wh - 1 >= 0) {
pq.push({a[i] - a[wh - 1], {i, wh - 1}});
}
} else {
if (wh + 1 < n) {
pq.push({a[wh + 1] - a[i], {i, wh + 1}});
}
}
}
}
