#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define x first
#define y second
typedef long long lint;
typedef pair<lint, lint> ii;
int n, K;
vector<ii> points;
vector<lint> ans;
set<ii> S;
inline lint get(int a, int b){
return max(abs(points[a].x - points[b].x), abs(points[a].y - points[b].y));
}
void solve(lint dis){
ans.clear();
S.clear();
int ptr = 0;
for(int i = 0;i < n;i++){
ii p = points[i];
while(true){
if(p.x - points[ptr].x <= dis) break;
else{
S.erase(ii(points[ptr].y, ptr));
ptr++;
}
}
auto it = S.lower_bound({p.y - dis, -1});
while(it != S.end()){
if(it->first > p.y + dis) break;
ans.push_back(get(it->second, i));
if(sz(ans) >= K) return;
it++;
}
S.insert(ii(p.y, i));
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> K;
for(int i = 1;i <= n;i++){
lint x, y; cin >> x >> y;
points.push_back(ii(x+y,x-y));
}
sort(all(points));
lint low = 0; lint high = 4e9;
while(low != high-1){
lint mid = (low+high)/2;
solve(mid);
if(sz(ans) >= K) high = mid;
else low = mid;
}
solve(low);
sort(all(ans));
while(sz(ans) < K) ans.push_back(high);
for(lint x : ans) cout << x << "\n";
}
