#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e10+7;
const int LIM=25e4+7;
vector<ll>wyn;
pair<ll,ll>T[LIM], P[LIM];
ll jaki[LIM], N=1, n, k;
pair<ll,ll>tr[4*LIM];
void upd(int v, ll x) {
v+=N;
tr[v]={x, v-N};
v/=2;
while(v) {
tr[v]=min(tr[2*v], tr[2*v+1]);
v/=2;
}
}
ll cnt(int l, int r) {
l+=N; r+=N;
pair<ll,ll>ans=min(tr[l], tr[r]);
while(l/2!=r/2) {
if(l%2==0) ans=min(ans, tr[l+1]);
if(r%2==1) ans=min(ans, tr[r-1]);
l/=2; r/=2;
}
return ans.nd;
}
void cl() {
rep(i, 2*N) tr[i]={INF, INF};
rep(i, n) tr[N+i].nd=i;
for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
}
void check(ll x) {
wyn.clear();
cl();
rep(xd, n) {
ll i=P[xd].nd;
vector<pair<ll,ll>>A;
while(wyn.size()<k) {
ll a=cnt(0, jaki[i]);
if(tr[N+a].st==INF) break;
ll b=T[i].st+T[i].nd+tr[N+a].st;
if(b>x) break;
wyn.pb(b);
A.pb({a, tr[N+a].st});
upd(a, INF);
}
for(auto j : A) upd(j.st, j.nd);
upd(jaki[i], -T[i].st-T[i].nd);
}
cl();
rep(xd, n) {
ll i=P[xd].nd;
vector<pair<ll,ll>>A;
while(wyn.size()<k) {
ll a=cnt(jaki[i], n-1);
if(tr[N+a].st==INF) break;
ll b=T[i].st-T[i].nd+tr[N+a].st;
if(b>x) break;
wyn.pb(b);
A.pb({a, tr[N+a].st});
upd(a, INF);
}
for(auto j : A) upd(j.st, j.nd);
upd(jaki[i], -T[i].st+T[i].nd);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
while(N<n) N*=2;
rep(i, n) cin >> T[i].st >> T[i].nd;
rep(i, n) P[i]={T[i].nd, i};
sort(P, P+n);
rep(i, n) jaki[P[i].nd]=i;
rep(i, n) P[i]={T[i].st, i};
sort(P, P+n);
ll po=0, ko=INF;
while(po<ko) {
ll sr=(po+ko+1)/2;
check(sr);
if(wyn.size()>=k) ko=sr-1; else po=sr;
}
check(po);
while(wyn.size()<k) wyn.pb(po+1);
sort(all(wyn));
for(auto i : wyn) cout << i << '\n';
}
