#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
struct persistent_segtree{
struct node{
pair<ll, int> mn;
int l, r;
node(){
mn = {inf, -1};
l = -1, r = -1;
}
node(pair<ll, int> _mn){
mn = _mn;
l = -1, r = -1;
}
node(pair<ll, int> _mn, int _l, int _r){
l = _l, r = _r, mn = _mn;
}
};
vector<node> v;
int k;
persistent_segtree(int n){
k = 1;
while(k <= n) k*=2; k*=2;
v.resize(k, node({inf, -1}));
for(int i = 0; i < k/2; i++) v[i].mn.sc = i;
for(int i = 1; 2*i+1 < k; i++) v[i].l = 2*i, v[i].r = 2*i+1, v[i].mn.sc = v[2*i].mn.sc;
}
int upd(int nd, int a, int b, int in, pair<ll, int> x){
if(a == b){
v.pb(node(x));
return (int)v.size() - 1;
}
int md = (a+b)/2;
if(in <= md){
int rt = upd(v[nd].l, a, md, in, x);
v.pb(node(min(v[v[nd].r].mn,v[rt].mn), rt, v[nd].r));
return (int)v.size()-1;
}
else{
int rt = upd(v[nd].r, md+1, b, in, x);
v.pb(node(min(v[v[nd].l].mn,v[rt].mn), v[nd].l, rt));
return (int)v.size()-1;
}
}
int upd(int nd, int in, ll x){
return upd(nd, 0, k/2-1, in, {x, in});
}
pair<ll, int> smn(int l, int r, int nd, int a, int b){
if(a > r || b < l){
return {inf, -1};
}
if(a >= l && b <= r){
return v[nd].mn;
}
int md = (a+b)/2;
return min(smn(l, r, v[nd].l, a, md), smn(l, r, v[nd].r, md+1, b));
}
pair<ll, int> smn(int nd, int l, int r){
return smn(l, r, nd, 0, k/2-1);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
vector<pair<ll, ll>> v(n);
for(auto &p: v) cin >> p.f >> p.sc;
sort(v.begin(), v.end());
vector<pair<ll, int>> yyy(n);
for(int i = 0; i < n; i++) yyy[i] = {v[i].sc, i};
vector<int> yy(n);
sort(yyy.begin(), yyy.end());
for(int i = 0; i < n; i++) yy[yyy[i].sc] = i;
persistent_segtree ps1(n), ps2(n);
priority_queue<tuple<ll, int, int, int>> pq;
int id = 1;
for(int i = 0; i < n; i++){
auto a = ps1.smn(id, 0, yy[i]);
auto b = ps2.smn(id, yy[i], n-1);
a.f+=v[i].f+v[i].sc;
b.f+=v[i].f-v[i].sc;
if(b.f < a.f) swap(a, b);
pq.push({-a.f, a.sc, id, i});
int id0 = ps1.upd(id, yy[i], -v[i].f-v[i].sc);
ps2.upd(id, yy[i], -v[i].f+v[i].sc);
id = id0;
}
while(k--){
auto [x, in, id, i] = pq.top();
x*=-1;
cout << x << "\n";
pq.pop();
int id0 = ps1.upd(id, in, inf);
ps2.upd(id, in, inf);
id = id0;
auto a = ps1.smn(id, 0, yy[i]);
auto b = ps2.smn(id, yy[i], n-1);
a.f+=v[i].f+v[i].sc;
b.f+=v[i].f-v[i].sc;
if(b.f < a.f) swap(a, b);
pq.push({-a.f, a.sc, id, i});
}
}
