#include <bits/stdc++.h>
#define ar array
//#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 3e5 + 5;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int n, K;
bool flag = 0;
ll cnt = 0, mid, need;
vector<ar<int, 2> > a(maxn);
vector<ll> vec;
Tree<pll> st;
bool cmp(ar<int, 2> x, ar<int, 2> y) {
return x[1] < y[1];
}
void dnc(int l, int r) {
if(l >= r) return ;
int tm = (l + r) / 2;
vector<ar<int, 2> > L, R;
for(int i=l; i<=tm; i++) L.push_back(a[i]);
for(int i=tm+1; i<=r; i++) R.push_back(a[i]);
sort(L.begin(), L.end(), cmp);
sort(R.begin(), R.end(), cmp);
st.clear();
int p = 0;
for(auto [x, y] : R) {
while(p < L.size() && L[p][1] < y) {
st.insert({ - L[p][0] - L[p][1], p });
p++;
}
if(!st.empty() && flag) {
auto it = st.begin();
while(it != st.end() && x + y + it->first <= mid) {
vec.push_back(x + y + it->first);
it++;
}
}
cnt += st.order_of_key({ mid - (x + y) + 1, 0 });
}
st.clear();
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
p = 0;
for(auto [x, y] : R) {
while(p < L.size() && L[p][1] >= y) {
st.insert({ - L[p][0] + L[p][1], p });
p++;
}
if(!st.empty() && flag) {
auto it = st.begin();
while(it != st.end() && x - y + it->first <= mid) {
vec.push_back(x - y + it->first);
it++;
}
}
cnt += st.order_of_key({ mid - x + y + 1, 0 });
}
dnc(l, tm);
dnc(tm+1, r);
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n >> K;
for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1];
sort(a.begin()+1, a.begin()+n+1);
ll l=0, r=4e9, ans=4e9;
while(l <= r) {
mid = (l + r) / 2;
cnt = 0;
need = K;
vec.clear();
dnc(1, n);
if(cnt >= K) ans = mid, r = mid - 1;
else l = mid + 1;
}
vec.clear();
flag = 1;
mid = ans - 1;
dnc(1, n);
while(vec.size() < K) vec.push_back(ans);
sort(vec.begin(), vec.end());
for(auto x : vec) cout << x << '\n';
}
