#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nx=250005, inf=1e9;
ll n, k, res=1e18, idxx;
pair<ll, ll> p[nx];
map<ll, vector<ll>> mp;
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;
struct persist
{
struct node
{
pair<ll, ll> mn;
node *l, *r;
node(pair<ll, ll> mn={1e18, 0}): mn(mn), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx], srt[nx];
void update(int l, int r, pnode &k, pnode t, int idx, ll vl)
{
//printf("update %d %d\n", l, r);
if (t) k=new node(*t);
else k=new node();
if (l==r) return k->mn={vl, idx}, void();
ll md=l+(r-l)/2;
if (idx<=md) update(l, md, k->l, t?t->l:0, idx, vl);
else update(md+1, r, k->r, t?t->r:0, idx, vl);
k->mn=min((k->l)?k->l->mn:make_pair((ll)1e18, (ll)0), (k->r)?k->r->mn:make_pair((ll)1e18, (ll)0));
}
pair<ll, ll> query(int l, int r, pnode k, int ql, int qr)
{
if (r<ql||qr<l|!k||qr<ql) return {1e18, 0};
if (ql<=l&&r<=qr) return k->mn;
ll md=l+(r-l)/2;
return min(query(l, md, k->l, ql, qr), query(md+1, r, k->r, ql, qr));
}
} up, dn;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>p[i].first>>p[i].second;
sort(p+1, p+n+1);
for (int i=1; i<=n; i++)
{
up.srt[i]=up.rt[i];
dn.srt[i]=dn.rt[i];
auto upq=up.query(-inf, inf, up.srt[i], p[i].second, inf);
upq.first+=p[i].first-p[i].second;
auto dnq=dn.query(-inf, inf, dn.srt[i], -inf, p[i].second-1);
dnq.first+=p[i].first+p[i].second;
auto tmp=min(upq, dnq);
//printf("here %d %lld %lld\n", i, tmp.first, tmp.second);
up.update(-inf, inf, up.rt[i+1], up.rt[i], p[i].second, -p[i].first+p[i].second);
dn.update(-inf, inf, dn.rt[i+1], dn.rt[i], p[i].second, -p[i].first-p[i].second);
if (tmp.first<1e10)
{
if (tmp.second>=p[i].second) up.update(-inf, inf, up.srt[i], up.srt[i], tmp.second, 1e18);
else dn.update(-inf, inf, dn.srt[i], dn.srt[i], tmp.second, 1e18);
idxx=mp[tmp.second].back();
pq.push({tmp.first, i, tmp.second, idxx});
}
mp[p[i].second].push_back(p[i].first);
}
for (int t=0; t<k; t++)
{
auto [w, idx, idxy, idxx]=pq.top();
pq.pop();
cout<<w<<'\n';
auto itr=lower_bound(mp[idxy].begin(), mp[idxy].end(), idxx);
if (itr!=mp[idxy].begin()) pq.push({w+*itr-*prev(itr), idx, idxy, *prev(itr)});
auto upq=up.query(-inf, inf, up.srt[idx], p[idx].second, inf);
upq.first+=+p[idx].first-p[idx].second;
auto dnq=dn.query(-inf, inf, dn.srt[idx], -inf, p[idx].second-1);
dnq.first+=+p[idx].first+p[idx].second;
auto tmp=min(upq, dnq);
if (tmp.first<1e10)
{
if (tmp.second>=p[idx].second) up.update(-inf, inf, up.srt[idx], up.srt[idx], tmp.second, 1e18);
else dn.update(-inf, inf, dn.srt[idx], dn.srt[idx], tmp.second, 1e18);
idxx=p[idx].first-(tmp.first-abs(p[idx].second-tmp.second));
pq.push({tmp.first, idx, tmp.second, idxx});
}
}
}
