#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
struct SegmentTree{
public:
ll n; vector<multiset<ll>> tree;
SegmentTree(ll N){
n = N;
tree.resize(4 * n);
}
void update(ll idx, ll val) {update(1, 0, n-1, idx, val);}
multiset<ll> query(ll l, ll r, ll T){
multiset<ll> rtv;
if(l > r) return rtv;
query(1, 0, n-1, l, r, T, rtv);
return rtv;
}
private:
void update(ll node, ll st, ll en, ll idx, ll val){
if(st == en) tree[node].insert(val);
else {
ll mid = (st + en)/2;
if(idx <= mid) update(2*node, st, mid, idx, val);
else update(2*node+1, mid+1, en, idx, val);
tree[node].insert(val);
}
}
void query(ll node, ll st, ll en, ll l, ll r, ll T, multiset<ll> &ms){
if(st > r || en < l) return;
if(l <= st && en <= r){
for(auto &c : tree[node]){
if(ms.size() == T && *(prev(ms.end())) <= c) break;
ms.insert(c);
if(ms.size() == T+1) ms.erase(prev(ms.end()));
}
} else {
ll mid = (st + en)/2;
query(2*node, st, mid, l, r, T, ms);
query(2*node+1, mid+1, en, l, r, T, ms);
}
}
};
ll getIdx(vector<ll> &cmp, ll x){
return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}
int main(){
fastio;
ll N, K; cin >> N >> K;
multiset<ll> ans;
vector<pii> coord(N);
vector<ll> xcmp, ycmp;
for(auto &[x,y] : coord) {
cin >> x >> y;
xcmp.push_back(x);
ycmp.push_back(y);
}
sort(xcmp.begin(), xcmp.end());
sort(ycmp.begin(), ycmp.end());
xcmp.erase(unique(xcmp.begin(), xcmp.end()), xcmp.end());
ycmp.erase(unique(ycmp.begin(), ycmp.end()), ycmp.end());
SegmentTree seg1(ycmp.size());
sort(coord.begin(), coord.end());
for(auto [x,y] : coord){
multiset<ll> ms = seg1.query(0, getIdx(ycmp, y)-1, 250);
for(auto c : ms) ans.insert(x+y+c);
seg1.update(getIdx(ycmp, y), -x-y);
}
SegmentTree seg2(ycmp.size());
for(auto [x,y] : coord){
multiset<ll> ms = seg2.query(getIdx(ycmp,y), ycmp.size(), 250);
for(auto c : ms) ans.insert(x-y+c);
seg2.update(getIdx(ycmp, y), -x+y);
}
for(auto c : ans){
if(K-- == 0) break;
cout << c << "\n";
}
}
