#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
struct point{
int x, y, id;
bool operator<(const point &other) const {
if(x == other.x) return y < other.y;
return x < other.x;
}
};
int dist(const point &a, const point &b){
return abs(a.x - b.x) + abs(a.y - b.y);
}
void solve(){
int n, k; cin >> n >> k;
vector<point> base(n);
priority_queue<int> pq;
for(int i = 0; i < k; i++) pq.push(inf);
for(int i = 0; i < n; i++){
cin >> base[i].x >> base[i].y;
base[i].id = i;
} sort(base.begin(), base.end());
int maxi = pq.top();
set<tuple<int, int, int>> sts;
for(int i = 0; i < n; i++){
tuple<int, int, int> tmp = make_tuple(base[i].y - maxi, -inf, base[i].id);
set<tuple<int, int, int>>::iterator it = sts.lower_bound(tmp);
while(it != sts.end() && get<0>(*it) <= base[i].y + maxi){
point cur = {get<1>(*it), get<0>(*it), get<2>(*it)};
if(dist(cur, base[i]) < maxi) {
pq.pop();
pq.push(dist(cur, base[i]));
maxi = pq.top();
} if(cur.x < base[i].x - maxi) it = sts.erase(it);
else it++;
} sts.insert({base[i].y, base[i].x, base[i].id});
} vector<int> rev_k(k);
for(int i = 0; i < k; i++) rev_k[i] = pq.top(), pq.pop();
for(int i = 0; i < k; i++) cout << rev_k[k - 1 - i] << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
while(test--) solve();
}
