#include<bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using p64x = pair<i64, int>;
static constexpr int digits = 19;
static constexpr i64 INF = 1e10;
struct seg {
seg *l,*r;
p64x mn;
seg() : l(),r(),mn(INF, 0){}
seg(p64x min_) : l(),r(),mn(min_){}
seg(seg *s, seg *e) : l(s),r(e),mn(min(s->mn,e->mn)){}
static seg init(int d = digits){
if(d==0)return {};--d;
auto c=new seg(init(d));
return {c,c};
}
p64x get_min(int s, int e, int ll = 0, int rr = 1 << digits) {
if (e<=ll||rr<=s)return {INF, 0};
if (s<=ll&&rr<=e)return mn;
int m=(ll+rr)/2;
return min(l->get_min(s,e,ll,m),r->get_min(s,e,m,rr));
}
seg update(int i, i64 v, int d = digits) {
if (d==0)return{{v,i}}; --d;
if (i >> d & 1)return {l, new seg(r->update(i, v, d))};
else return {new seg(l->update(i, v, d)), r};
}
};
struct cpr {
vector<p64x> v;
void add(p64x x){v.push_back(x);}
void build(){sort(v.begin(),v.end());}
int get(p64x x){return lower_bound(v.begin(),v.end(), x)-v.begin();}
};
struct town{i64 x,y;};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k; cin>>n>>k;
vector<town>towns(n);
for (auto &[x,y]:towns)cin >> x >> y;
sort(towns.begin(), towns.end(),[&](const auto &l,const auto &r){return l.x<r.x;});
cpr yc;
for (int i=0;i<n;i++) {
const auto &[x,y]=towns[i];
yc.add({y, i});
}
yc.build();
vector<seg> u(n + 1), d(n + 1);
u[0]=seg::init();
d[0]=seg::init();
for(int i=0;i<n;i++) {
const auto &[x,y]=towns[i];
const int pos=yc.get({y,i});
u[i + 1]=u[i].update(pos,-x + y);
d[i + 1]=d[i].update(pos,-x - y);
}
priority_queue<p64x, vector<p64x>, greater<p64x>> que;
const auto push = [&](const int i) {
const auto &[x,y] = towns[i];
const int pos = yc.get({y, i});
const auto [um, ui] = u[i].get_min(pos, 1 << digits);
const auto [dm, di] = d[i].get_min(0, pos);
if (um == INF && dm == INF)return;
if (um + x - y < dm + x + y) {
que.push({um + x - y, i});
u[i] = u[i].update(ui, INF);
}else{
que.push({dm + x + y, i});
d[i] = d[i].update(di, INF);
}
};
for (int i=0;i<n;i++)push(i);
for (int i=0;i<k;i++) {
const auto [c,j]=que.top();que.pop();
cout<<c<<'\n'; push(j);
} return 0;
}
