#include<bits/stdc++.h>
using namespace std ;
#define MAXN 250007
int n , k ;
pair < int , int > a[ MAXN ] ;
int ord[ MAXN ] ;
set < int > ys ;
map < int , int > cm ;
int ctr = 0 ;
priority_queue < long long > hh ;
long long ans[ MAXN ] ;
int mx_coord ;
class Tree {
public :
multiset < int > small[ 4 * MAXN ] , large[ 4 * MAXN ] ;
void init ( int where , int IL , int IR ) {
small[ where ].clear ( ) ;
large[ where ].clear ( ) ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void ins ( int where , int IL , int IR , int pos , int x , int y ) {
small[ where ].insert ( - x - y ) ;
large[ where ].insert ( - x + y ) ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) {
ins ( 2 * where , IL , mid , pos , x , y ) ;
}
else {
ins ( 2 * where + 1 , mid + 1 , IR , pos , x , y ) ;
}
}
void proc ( int where , int IL , int IR , int CURL , int CURR , long long fw , bool fl ) {
if ( IL > IR || CURL > CURR ) { return ; }
if ( IR < CURL || CURR < IL ) { return ; }
if ( CURL <= IL && IR <= CURR ) {
multiset < int > :: iterator it ;
multiset < int > :: iterator en ;
if ( fl == true ) { it = small[ where ].begin ( ) , en = small[ where ].end ( ) ; }
else { it = large[ where ].begin ( ) , en = large[ where ].end ( ) ; }
while ( it != en ) {
hh.push ( fw + (*it) ) ;
while ( hh.size ( ) > k ) {
int aux = hh.top ( ) ;
hh.pop ( ) ;
if ( aux == fw + (*it) ) { return ; }
}
++ it ;
}
return ;
}
int mid = ( IL + IR ) / 2 ;
proc ( 2 * where , IL , mid , CURL , CURR , fw , fl ) ;
proc ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , fw , fl ) ;
}
};
Tree w ;
bool f ( long long sr , bool inc ) {
return true ;
}
void input ( ) {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ].first >> a[ i ].second ;
ys.insert ( a[ i ].second ) ;
}
sort ( a + 1 , a + n + 1 ) ;
int tp = 0 ;
for ( auto val : ys ) {
cm[ val ] = ++ tp ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
ord[ i ] = cm[ a[ i ].second ] ;
}
mx_coord = tp ;
}
void solve ( ) {
w.init ( 1 , 1 , mx_coord ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
w.proc ( 1 , 1 , mx_coord , 1 , ord[ i ] , 0LL + a[ i ].first + a[ i ].second , true ) ;
w.proc ( 1 , 1 , mx_coord , ord[ i ] + 1 , mx_coord , 0LL + a[ i ].first - a[ i ].second , false ) ;
w.ins ( 1 , 1 , mx_coord , ord[ i ] , a[ i ].first , a[ i ].second ) ;
}
ctr = k ;
while ( hh.empty ( ) == false ) {
ans[ ctr -- ] = hh.top ( ) ;
hh.pop ( ) ;
}
for ( int i = 1 ; i <= k ; ++ i ) {
cout << ans[ i ] << "\n" ;
}
}
int main ( ) {
//freopen ( "dictionary.in" , "r" , stdin ) ;
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
