#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define MAXN 250007
int n , k ;
pair < ll , ll > a[ MAXN ] ;
int ord[ MAXN ] , mx_coord ;
class Tree {
public :
int tr[ MAXN ] ;
void init ( ) {
for ( int i = 0 ; i <= mx_coord ; ++ i ) {
tr[ i ] = 0 ;
}
}
void update ( int wh , int x ) {
for ( int i = wh ; i <= mx_coord ; i += ( i & ( -i ) ) ) {
tr[ i ] += x ;
}
}
int query ( int wh ) {
int ret = 0 ;
for ( int i = wh ; i > 0 ; i -= ( i & ( -i ) ) ) {
ret += tr[ i ] ;
}
return ret ;
}
};
Tree w ;
set < ll > s ;
map < ll , ll > cm ;
void input ( ) {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; ++ i ) {
int x , y ;
cin >> x >> y ;
a[ i ] = { x + y , x - y } ;
s.insert ( a[ i ].second ) ;
}
sort ( a + 1 , a + n + 1 ) ;
int tp = 0 ;
for ( auto val : s ) {
cm[ val ] = ++ tp ;
}
for ( int i = 1 ; i <= n ; ++ i ) {
ord[ i ] = cm[ a[ i ].second ] ;
}
mx_coord = tp ;
}
bool f ( long long sr ) {
w.init ( ) ;
int st = 0 ;
int cnt = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
while ( 0LL + a[ i ].first - a[ st + 1 ].first > sr ) {
w.update ( ord[ st + 1 ] , -1 ) ;
++ st ;
}
auto lw = s.lower_bound ( a[ i ].second - sr ) ;
auto hg = s.upper_bound ( a[ i ].second + sr ) ;
-- hg ;
cnt += w.query ( cm[ *hg ] ) - w.query ( cm[ *lw ] - 1 ) ;
w.update ( ord[ i ] , 1 ) ;
if ( cnt >= k ) { return true ; }
}
return false ;
}
set < pair < ll , int > > aux ;
vector < ll > ans ;
void calc ( long long sr ) {
int st = 0 ;
int cnt = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
while ( 0LL + a[ i ].first - a[ st + 1 ].first > sr ) {
aux.erase ( { a[ st + 1 ].second , st + 1 } ) ;
++ st ;
}
if ( aux.empty ( ) == false ) {
auto it1 = aux.lower_bound ( { a[ i ].second , -1 } ) ;
auto it2 = it1 ;
while ( it1 != aux.end ( ) ) {
if ( it1->first - a[ i ].second > sr ) { break ; }
ans.push_back ( max ( it1->first - a[ i ].second , a[ i ].first - a[ it1->second ].first ) ) ;
++ cnt ;
++ it1 ;
}
if ( it2 != aux.begin ( ) ) {
-- it2 ;
while ( 1 ) {
if ( a[ i ].second - it2->first > sr ) { break ; }
ans.push_back ( max ( a[ i ].second - it2->first , a[ i ].first - a[ it2->second ].first ) ) ;
++ cnt ;
if ( it2 == aux.begin ( ) ) { break ; }
-- it2 ;
}
}
}
aux.insert ( { a[ i ].second , i } ) ;
}
while ( cnt < k ) {
++ cnt ;
ans.push_back ( sr + 1 ) ;
}
sort ( ans.begin ( ) , ans.end ( ) ) ;
for ( int i = 0 ; i < k ; ++ i ) {
cout << ans[ i ] << "\n" ;
}
}
void solve ( ) {
long long l , r , mid ;
l = 1 , r = 1e10 ;
while ( r - l > 3 ) {
mid = ( l + r ) / 2 ;
if ( f ( mid ) == true ) { r = mid ; }
else { l = mid ; }
}
while ( f ( r ) == true ) { -- r ; }
calc ( r ) ;
}
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 ;
}
