#include <bits/stdc++.h>
#define ar array
using namespace std;
using ll = long long;
#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>;
ll n, K;
vector<ar<ll, 2> > a;
Tree<pair<ll, ll> > st;
vector<ll> vec;
ll get(ll l, ll r) {
return st.order_of_key({ r+1, 0 }) - st.order_of_key({ l, 0 });
}
bool f(ll d, bool flag) {
ll cnt = 0;
int p = 1;
st.clear();
for(int i=1; i<=n; i++) {
while(p < i && a[i][0] - a[p][0] > d) {
st.erase({ a[p][1], p });
p++;
}
cnt += get(a[i][1] - d, a[i][1] + d);
if(flag && get(a[i][1]-d, a[i][1]+d) > 0) {
auto it = st.lower_bound({ a[i][1]-d, 0 });
while(it != st.end() && it->first <= a[i][1]+d) {
ll x = abs(a[i][0] - a[it->second][0]);
ll y = abs(a[i][1] - it->first);
vec.push_back(max( x, y ));
it++;
}
}
st.insert({ a[i][1], i });
}
return (cnt >= K);
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n >> K;
a.push_back({ 0, 0 });
for(int i=1; i<=n; i++) {
int x, y; cin >> x >> y;
a.push_back({ x - y, x + y });
}
sort(a.begin()+1, a.begin()+n+1);
ll l=0, r=4e9, ans=4e9;
while(l <= r) {
ll mid = (l + r) / 2;
if(f(mid, 0)) ans = mid, r = mid - 1;
else l = mid + 1;
}
f(ans-1, 1);
while(vec.size() < K) vec.push_back(ans);
sort(vec.begin(), vec.end());
for(auto x : vec) cout << x << '\n';
}
