#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
const int MAX = 250010;
int n,k;
pair<int,int> a[MAX];
int ans[MAX];
struct cmp{
bool operator () (const pair<int,int> &a,const pair<int,int> &b) const {
if(a.S == b.S) return a.F < b.F;
return a.S < b.S;
}
};
int getl = 0;
bool chk(int len){
deque<pair<int,int>> q;
multiset<pair<int,int>,cmp> st;
int tot = 0;
for(int i = 1;i <= n;i++){
while(!q.empty() && a[i].F - q.front().F > len){
st.erase(st.find(q.front()));
q.pop_front();
}
auto it = st.lower_bound({-1e18,a[i].S - len});
while(it != st.end() && abs((*it).S - a[i].S) <= len){
ans[++tot] = max(a[i].F - (*it).F,abs((*it).S - a[i].S));
if(tot >= k) return 1;
++it;
}
q.push_back(a[i]); st.insert(a[i]);
}
getl = tot;
return 0;
}
signed main(){
//freopen("DuongDenLop.inp","r",stdin);
//freopen("DuongDenLop.out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i++) {
int x,y;cin >> x >> y;
a[i] = {x - y,x + y};
}
sort(a + 1,a + n + 1);
int re = 0;
for(int i = 40;i >= 0;i--){
if(!chk(re + (1ll << i))) re += (1ll << i);
}
chk(re);
sort(ans + 1,ans + getl + 1);
int i = 1;
while(i <= getl && i <= k){
cout << ans[i] << '\n';
i++;
}
while(i <= k){
cout << re + 1 << '\n';
i++;
}
}
