#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii ;
typedef pair<ll, ll> pll ;
typedef vector<pii> vii ;
typedef vector<int> veci ;
typedef vector<pll> vll ;
typedef vector<ll> vecll;
// find_by_order order_of_key
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define set_dec(x) cout << fixed << setprecision(x);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb lower_bound
#define ub upper_bound
#define for1(n) for(int i=1;i<=n;i++)
#define for0(n) for(int i=0;i<n;i++)
#define forn(n) for(int i=n;i>0;i--)
#define pq priority_queue <int, vector<int>, greater<int>>
const ll mod=4e9+2;
const int N=1<<18;
int n,m,k,o,kk;
vector<int>vecc;
ll d;
pii A[N];
pq seg[N*2];
pq segg[N*2];
vector<int>vec;
vector<ll>ans;
void get(int i,int x,int y,int l=0,int r=vecc.size(),int v=1){
while(kk && seg[v].size() && seg[v].top()<=d-x-y){
vec.pb(seg[v].top());
seg[v].pop();
kk--;
}
for(ll t:vec){
seg[v].push(t);
if(o)ans.pb(t+x+y);
}
vec.clear();
while(kk && segg[v].size() && segg[v].top()<=d-x+y){
vec.pb(segg[v].top());
segg[v].pop();
kk--;
}
for(ll t:vec){
segg[v].push(t);
if(o)ans.pb(t+x-y);
}
vec.clear();
if(r-l==1)return;
int mid=(l+r)>>1;
if(i<mid)get(i,x,y,l,mid,v<<1);
else get(i,x,y,mid,r,v<<1|1);
}
void upd(int lx,int x,int l=0,int r=vecc.size(),int v=1){
if(lx>=r)return;
if(lx<=l){
seg[v].push(x);
return;
}
int mid=(l+r)>>1;
upd(lx,x,l,mid,v<<1);
upd(lx,x,mid,r,v<<1|1);
}
void updd(int rx,int x,int l=0,int r=vecc.size(),int v=1){
if(rx<=l)return;
if(r<=rx){
segg[v].push(x);
return;
}
int mid=(l+r)>>1;
updd(rx,x,l,mid,v<<1);
updd(rx,x,mid,r,v<<1|1);
}
bool check(ll dd){
d=dd;
kk=k;
for1(n){
get(A[i].S,A[i].F,vecc[A[i].S]);
upd(A[i].S,-A[i].F-vecc[A[i].S]);
updd(A[i].S,-A[i].F+vecc[A[i].S]);
}
for0(N*2){
while(seg[i].size())
seg[i].pop();
while(segg[i].size())
segg[i].pop();
}
return (kk==0);
}
int main(){
fast_io
cin>>n>>k;
for1(n){
cin>>A[i].F>>A[i].S;
vecc.pb(A[i].S);
}
sort(A+1,A+n+1);
sort(all(vecc));vecc.resize(unique(all(vecc))-vecc.begin());
for1(n)A[i].S=lb(all(vecc),A[i].S)-vecc.begin();
ll l=0,r=mod;
while(r-l!=1){
ll mid=(l+r)>>1;
if(check(mid)==0)l=mid;
else r=mid;
}
o=1;
check(l);
sort(all(ans));
for(ll x:ans)cout<<x<<endl;
for1(k-ans.size())cout<<l+1<<endl;
}
