#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct node {
int l, r;
pair<ll, int> v;
node() : l(0), r(0), v(1e18, 0) {}
}nd[1<<25];
int nc;
void upd(int i, int i_, int s, int e, int t, ll v) {
if (s==e) {
nd[i].v={v, s};
return ;
}
int m=(s+e)/2;
if (t<=m) {
nd[i].l=++nc;
nd[i].r=nd[i_].r;
upd(nc, nd[i_].l, s, m, t, v);
}else {
nd[i].l=nd[i_].l;
nd[i].r=++nc;
upd(nc, nd[i_].r, m+1, e, t, v);
}
nd[i].v=min(nd[nd[i].l].v, nd[nd[i].r].v);
}
pair<ll, int> get(int i, int s, int e, int l, int r) {
if (!i||r<l||e<l||r<s) return {1e18, 0};
if (l<=s&&e<=r) return nd[i].v;
int m=(s+e)/2;
return min(get(nd[i].l, s, m, l, r), get(nd[i].r, m+1, e, l, r));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin>>n>>k;
vector<pair<ll, ll>> p(n);
for (auto &i:p) cin>>i.first>>i.second;
sort(all(p));
vector<int> ys(n), yi(n), b(n);
for (int i=0; i<n; i++) ys[i]=i;
sort(all(ys), [&](int x, int y) { return p[x].second<p[y].second; });
for (int i=0; i<n; i++) {
int j=i;
for (; j<n&&p[ys[i]].second==p[ys[j]].second; j++) {
b[ys[j]]=i;
yi[ys[j]]=j;
}
i=j-1;
}
vector<int> ur(n), dr(n);
priority_queue<pair<ll, int>> pq;
for (int i=1; i<n; i++) {
ur[i]=++nc;
upd(nc, ur[i-1], 0, n-1, yi[i-1], -p[i-1].first+p[i-1].second);
dr[i]=++nc;
upd(nc, dr[i-1], 0, n-1, yi[i-1], -p[i-1].first-p[i-1].second);
}
auto up = [&](int i) {
auto k=get(ur[i], 0, n-1, b[i], n-1);
pq.emplace(-(p[i].first-p[i].second+k.first), i);
int x=++nc;
upd(x, ur[i], 0, n-1, k.second, 1e18);
ur[i]=x;
};
auto down = [&](int i) {
auto k=get(dr[i], 0, n-1, 0, b[i]-1);
pq.emplace(-(p[i].first+p[i].second+k.first), i+n);
int x=++nc;
upd(x, dr[i], 0, n-1, k.second, 1e18);
dr[i]=x;
};
for (int i=1; i<n; i++) up(i), down(i);
while (k--) {
auto [v, i]=pq.top();
pq.pop();
cout<<-v<<'\n';
if (i<n) up(i);
else down(i-n);
}
return 0;
}
