#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int inf = 1e9 + 7;
const ll Binf = 1e18;
struct T {
vector <ll> t[2];
vector <ll> fn;
int n, ql, qr, qi, k, qd, ia;
ll qx;
void init(int sz, int kx) {
n = sz, sz += 5; k = kx;
t[0].assign(sz << 2, -Binf);
t[1].assign(sz << 2, -Binf);
}
void update(int v, int l, int r) {
if (l == r)
return t[qd][v] = qx, void();
int m = l + r >> 1;
if (qi <= m)
update(v << 1, l, m);
else
update(v << 1 | 1, m + 1, r);
t[qd][v] = max(t[qd][v << 1], t[qd][v << 1 | 1]);
}
void upd(int i, ll x, ll x2) {
qi = i, qx = x, qd = 0;
update(1, 1, n);
qi = i, qx = x2, qd = 1;
update(1, 1, n);
}
int get(int v, int l, int r) {
if (k <= 0 || ql > r || l > qr)
return 0;
int m = l + r >> 1;
if (ql <= l && r <= qr) {
if (l == r) {
if (t[qd][v] >= qx) {
k--;
if (ia)
fn.emplace_back(qx - t[qd][v]);
return 1;
}
return 0;
}
int ans = 0;
if (t[qd][v << 1] >= qx)
ans += get(v << 1, l, m);
if (t[qd][v << 1 | 1] >= qx)
ans += get(v << 1 | 1, m + 1, r);
return ans;
}
return get(v << 1, l, m) + get(v << 1 | 1, m + 1, r);
}
int query(int l, int r, ll x, int d, int add) {
if (l > r)
return 0;
ql = l, qr = r, qx = x, qd = d, ia = add;
return get(1, 1, n);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector <ar <ll, 3>> a(n);
vector <ll> b; b.emplace_back(-inf);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
a[i][2] = a[i][1];
b.emplace_back(a[i][1]);
}
sort(all(b));
for (int i = 0; i < n; i++) {
a[i][1] = lower_bound(all(b), a[i][1]) - b.begin();
b[a[i][1]] = b[a[i][1] - 1];
}
sort(all(a));
ll l = -1, r = 1e15;
while (l + 1 < r) {
ll m = l + r >> 1;
T st; st.init(n, k + 5);
ll res = 0;
for (auto now : a) {
res += st.query(1, now[1], now[0] + now[2] - m, 0, 0) + st.query(now[1] + 1, n, now[0] - now[2] - m, 1, 0);
st.upd(now[1], now[0] + now[2], now[0] - now[2]);
}
if (res >= k)
r = m;
else
l = m;
}
ll res = 0;
T st; st.init(n, k + 5);
for (auto now : a) {
res += st.query(1, now[1], now[0] + now[2] - (r - 1), 0, 1) + st.query(now[1] + 1, n, now[0] - now[2] - (r - 1), 1, 1);
st.upd(now[1], now[0] + now[2], now[0] - now[2]);
}
sort(all(st.fn));
for (int i = 0; i < k; i++) {
if (i >= st.fn.size()) {
cout << r << '\n';
} else {
cout << st.fn[i] + r - 1 << '\n';
}
}
}
