#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mxn=2e5+5e4+10,inf=1e18,lg=30,mx=1e9,nx=-1e9,minf=-1e18,mod=998244353;
/*
find k cheapest road
we can get the cheapest road for i node with sparse seg?
persist sparse segtee ??TT
persist is alrdy sparse?
*/
int n,k;
struct node{
pair<pii,pii> val;
node*l,*r;
node():val({{inf,inf},{inf,inf}}),l(0),r(0){};
};
map<int32_t,vector<int32_t>>mp;
map<int32_t,int32_t>cnt[mxn+10];
struct persist{
node *root[mxn+10];
pii get(node *x){return (x==NULL)?make_pair(inf,inf):x->val.f;}
pii get2(node *x){return (x==NULL)?make_pair(inf,inf):x->val.s;}
void update(int l,int r,node *last,node *&cur,int pos,int val,int val2){
if(last==NULL)cur=new node();
else cur=new node(*last);
if(l==r){
return void(cur->val={{val,pos},{val2,pos}});
}
int mid=l+(r-l)/2;
if(pos<=mid)update(l,mid,((last==NULL)?last:last->l),cur->l,pos,val,val2);
else update(mid+1,r,((last==NULL)?last:last->r),cur->r,pos,val,val2);
cur->val.f=min(get(cur->l),get(cur->r));
cur->val.s=min(get2(cur->l),get2(cur->r));
}
pii qry(int l,int r,node *cur,int ql,int qr,int mode){
if(cur==NULL||l>qr||r<ql)return {inf,inf};
if(ql<=l&&r<=qr){
if(mode)return cur->val.s;
return cur->val.f;
}
int mid=l+(r-l)/2;
return min(qry(l,mid,cur->l,ql,qr,mode),qry(mid+1,r,cur->r,ql,qr,mode));
}
}t;
int32_t main(){
fastio
cin>>n>>k;
vector<pii>v(n);
for(int i=0;i<n;i++)cin>>v[i].f>>v[i].s;
sort(all(v));
for(int i=0;i<n;i++)mp[v[i].s].pb(i);
for(int i=1;i<n;i++)t.update(nx,mx,t.root[i-(i!=0)],t.root[i],v[i-1].s,-v[i-1].f+v[i-1].s,-v[i-1].f-v[i-1].s);
auto del=[&](int x,int pos){
if(cnt[x].find(pos)==cnt[x].end())cnt[x][pos]=upper_bound(all(mp[pos]),x-1)-mp[pos].begin()-1;
cnt[x][pos]--;
return ((cnt[x][pos]<0)?inf:v[mp[pos][cnt[x][pos]]].f);
};
auto get=[&](int x){
pii a=t.qry(nx,mx,t.root[x],v[x].s,mx,0),b=t.qry(nx,mx,t.root[x],nx,v[x].s-1,1);
int up;
if(max(minf,a.f-v[x].s)<min(inf,b.f+v[x].s)){
if(a.s==inf)return inf;
up=del(x,a.s);
if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],a.s,-up+a.s,-up-a.s);
else t.update(nx,mx,t.root[x],t.root[x],a.s,inf,inf);
return v[x].f+a.f-v[x].s;
}
else{
if(b.s==inf)return inf;
up=del(x,b.s);
if(up!=inf)t.update(nx,mx,t.root[x],t.root[x],b.s,-up+b.s,-up-b.s);
else t.update(nx,mx,t.root[x],t.root[x],b.s,inf,inf);
return v[x].f+b.f+v[x].s;
}
};
priority_queue<pii,vector<pii>,greater<pii>>pq;
for(int i=0;i<n;i++)pq.push({get(i),i});
for(int i=0;i<k;i++){
if(pq.empty())assert(0);
cout<<pq.top().f<<"\n";
int x=pq.top().s;
pq.pop();
pq.push({get(x),x});
}
}
/*
3 3
-1 0
0 2
0 0
5 4
1 -1
2 0
-1 0
0 2
0 -2
4 6
0 0
1 0
3 0
4 0
*/
