#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 25e4+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n, k;
pii seg[4*MAXN];
vector<pii> p, add, sub;
vector<int> ord;
void update(int node, int l, int r, int ind, pii val) {
if(l == r) {
seg[node] = val;
return;
}
int mid = (l+r)/2;
if(ind <= mid) update(2*node, l, mid, ind, val);
else update(2*node+1, mid+1, r, ind, val);
seg[node] = max(seg[2*node], seg[2*node+1]);
}
pii query(int node, int l, int r, int p, int q) { // flag = 1 pra mínimo e -1 pra máximo
if(r < p or q < l) return {-2e9, -1};
if(p <= l and r <= q) return seg[node];
int mid = (l+r)/2;
return max(query(2*node, l, mid, p, q), query(2*node+1, mid+1, r, p, q));
}
bool check(ll X, vector<ll> &ans) {
ans.clear();
fill(seg, seg+4*n+1, mk(-2e9, -1));
for(int i = 0; i < n; i++) {
vector<int> re_add = {i};
while(sz(ans) < k) {
int ptr = lower_bound(all(add), mk(p[i].fr + p[i].sc, 0)) - add.begin();
auto [val,j] = query(1, 0, n-1, ptr, n-1); // procurar o máximo x - y
if(j == -1 or (ll)p[i].fr - (ll)p[i].sc - (ll)val > X) break;
ans.pb((ll)p[i].fr - (ll)p[i].sc - (ll)val);
re_add.pb(j);
ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
update(1, 0, n-1, ptr, {-2e9, -1});
}
for(int j : re_add) {
int ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
update(1, 0, n-1, ptr, {p[j].fr - p[j].sc, j});
}
}
fill(seg, seg+4*n+1, mk(-2e9, -1));
for(int i = 0; i < n; i++) {
vector<int> re_add = {i};
while(sz(ans) < k) {
int ptr = lower_bound(all(sub), mk(p[i].fr - p[i].sc, 0)) - sub.begin();
auto [val,j] = query(1, 0, n-1, ptr, n-1); // procurar o máximo x + y
if(j == -1 or (ll)p[i].fr + (ll)p[i].sc - (ll)val > X) break;
ans.pb((ll)p[i].fr + (ll)p[i].sc - (ll)val);
re_add.pb(j);
ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
update(1, 0, n-1, ptr, {-2e9, -1});
}
for(int j : re_add) {
int ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
update(1, 0, n-1, ptr, {p[j].fr + p[j].sc, j});
}
}
fill(seg, seg+4*n+1, mk(-2e9, -1));
for(int i : ord) {
vector<int> re_add = {i};
while(sz(ans) < k) {
int ptr = lower_bound(all(sub), mk(p[i].fr - p[i].sc, 0)) - sub.begin();
auto [val,j] = query(1, 0, n-1, 0, ptr - 1); // procurar o máximo x + y
if(j == -1 or (ll)p[i].fr + (ll)p[i].sc - (ll)val > X) break;
ans.pb((ll)p[i].fr + (ll)p[i].sc - (ll)val);
re_add.pb(j);
ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
update(1, 0, n-1, ptr, {-2e9, -1});
}
for(int j : re_add) {
int ptr = lower_bound(all(sub), mk(p[j].fr - p[j].sc, j)) - sub.begin();
update(1, 0, n-1, ptr, {p[j].fr + p[j].sc, j});
}
}
reverse(all(ord));
fill(seg, seg+4*n+1, mk(-2e9, -1));
for(int i : ord) {
vector<int> re_add = {i};
while(sz(ans) < k) {
int ptr = lower_bound(all(add), mk(p[i].fr + p[i].sc, 0)) - add.begin();
auto [val,j] = query(1, 0, n-1, 0, ptr - 1); // procurar o máximo x - y
if(j == -1 or (ll)p[i].fr - (ll)p[i].sc - (ll)val > X) break;
ans.pb((ll)p[i].fr - (ll)p[i].sc - (ll)val);
re_add.pb(j);
ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
update(1, 0, n-1, ptr, {-2e9, -1});
}
for(int j : re_add) {
int ptr = lower_bound(all(add), mk(p[j].fr + p[j].sc, j)) - add.begin();
update(1, 0, n-1, ptr, {p[j].fr - p[j].sc, j});
}
}
reverse(all(ord));
if(sz(ans) < k) return 0;
return 1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
p.resize(n);
ord.resize(n);
for(int i = 0; i < n; i++) {
cin >> p[i].fr >> p[i].sc;
ord[i] = i;
}
sort(all(p));
sort(all(ord), [](int a, int b){
return mk(p[a].sc, p[a].fr) <= mk(p[b].sc, p[b].fr);
});
for(int i = 0; i < n; i++) {
add.pb({p[i].fr + p[i].sc, i});
sub.pb({p[i].fr - p[i].sc, i});
}
sort(all(add));
sort(all(sub));
ll l = 0, r = 4e9;
vector<ll> ans;
while(l <= r) {
ll mid = (l+r)/2;
if(check(mid, ans)) r = mid-1;
else l = mid+1;
}
check(r, ans);
while(sz(ans) < k) ans.pb(r+1);
sort(all(ans));
for(ll it : ans) cout << it << "\n";
}
