#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 25e4 + 5;
const ll LIM = 4e9;
int n, k;
ll x[lim], y[lim];
namespace sub1{
void solve(){
vector<ll>a;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
a.emplace_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
}
}
sort(a.begin(), a.end());
for(int i = 0; i < k; i++){
cout << a[i] << "\n";
}
}
}
namespace sub2{
void solve(){
sort(x + 1, x + n + 1);
ll low = 1, high = LIM, d;
while(low <= high){
ll mid = (low + high) >> 1LL;
int cnt = 0;
for(int i = 1, j = 1; i <= n && cnt < k; i++){
while(x[i] - x[j] > mid){
j++;
}
cnt += i - j;
}
if(cnt >= k){
high = (d = mid) - 1;
}
else{
low = mid + 1;
}
}
vector<ll>ans;
for(int i = 1; i <= n; i++){
for(int j = i - 1; j > 0 && x[i] - x[j] < d; j--){
ans.emplace_back(x[i] - x[j]);
}
}
sort(ans.begin(), ans.end());
for(ll& x : ans){
cout << x << "\n";
}
for(int i = ans.size(); i < k; i++){
cout << d << "\n";
}
}
}
namespace sub3456{
const int LIM_NODE = 45e5;
struct Node{
int cnt, l, r;
Node(){
this->cnt = 0;
this->l = this->r = -1;
}
};
int N_y, cnt_node;
vector<ll>_x(1, -LLONG_MAX), _y(1, -LLONG_MAX);
Node st[LIM_NODE];
void build(int id, int l, int r){
if(l == r){
return;
}
int m = (l + r) >> 1;
build(st[id].l = cnt_node++, l, m);
build(st[id].r = cnt_node++, m + 1, r);
}
void update(int id, int l, int r, int p){
st[id].cnt++;
if(l == r){
return;
}
int m = (l + r) >> 1;
if(m < p){
st[cnt_node] = st[st[id].r];
update(st[id].r = cnt_node++, m + 1, r, p);
}
else{
st[cnt_node] = st[st[id].l];
update(st[id].l = cnt_node++, l, m, p);
}
}
int get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return 0;
}
if(u <= l && v >= r){
return st[id].cnt;
}
ll m = (l + r) >> 1LL;
return get(st[id].l, l, m, u, v) + get(st[id].r, m + 1, r, u, v);
}
int get(ll X, ll yl, ll yr){
return get(upper_bound(_x.begin(), _x.end(), X) - _x.begin() - 1, 0, N_y - 1, lower_bound(_y.begin(), _y.end(), yl) - _y.begin(), upper_bound(_y.begin(), _y.end(), yr) - _y.begin() - 1);
}
void solve(){
for(int i = 1; i <= n; i++){
_x.emplace_back(x[i] += y[i]);
_y.emplace_back(y[i] = x[i] - (y[i] << 1LL));
}
sort(_x.begin(), _x.end());
_x.resize(unique(_x.begin(), _x.end()) - _x.begin());
sort(_y.begin(), _y.end());
_y.resize(unique(_y.begin(), _y.end()) - _y.begin());
N_y = _y.size();
vector<int>p(n);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j){
return x[i] < x[j];
});
cnt_node = _x.size();
build(0, 0, N_y - 1);
int j = 0;
for(int& i : p){
if(x[i] != _x[j]){
j++;
st[j] = st[j - 1];
}
update(j, 0, N_y - 1, lower_bound(_y.begin(), _y.end(), y[i]) - _y.begin());
}
ll low = 1, high = LIM, d;
while(low <= high){
ll mid = (low + high) >> 1LL;
int cnt = 0;
bool flag = false;
for(int i = 1; i <= n && (cnt >> 1) < k; i++){
cnt += get(x[i] + mid, y[i] - mid, y[i] + mid) - get(x[i] - mid - 1, y[i] - mid, y[i] + mid) - 1;
}
if((cnt >> 1) >= k){
high = (d = mid) - 1;
}
else{
low = mid + 1;
}
}
set<pair<ll, ll>>S;
vector<ll>ans;
if(d > 1){
for(int i = 0, j = 0; i < n; i++){
while(x[p[i]] - x[p[j]] >= d){
S.erase(make_pair(y[p[j]], x[p[j]]));
j++;
}
for(auto it = S.lower_bound(make_pair(y[p[i]] - d + 1, -1)); it != S.end() && (*it).first < y[p[i]] + d; it = next(it)){
ans.emplace_back(max(abs(x[p[i]] - (*it).second), abs(y[p[i]] - (*it).first)));
}
S.emplace(y[p[i]], x[p[i]]);
}
sort(ans.begin(), ans.end());
for(ll& x : ans){
cout << x << "\n";
}
}
for(int i = ans.size(); i < k; i++){
cout << d << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
}
if(n <= 1000){
sub1::solve();
}
else if(count(y + 1, y + n + 1, 0) == n){
sub2::solve();
}
else{
sub3456::solve();
}
}
