#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k,pos;
struct node
{
    int x, y,id;
} a[250005];
bool cmp(node a, node b)
{
    return a.x < b.x || a.x == b.x && a.y < b.y;
}
bool cmp2(node a,node b){
    return a.y<b.y;
}
int val[250005];
map<int,int> mp;
int findsuf(int x){
    int lt=0,rt=pos+1;
    while(lt+1<rt){
        int mid=lt+rt>>1;
        if(val[mid]>=x){
            rt=mid;
        }
        else{
            lt=mid;
        }
    }
    return rt;
}
int findpre(int x){
    int lt=0,rt=pos+1;
    while(lt+1<rt){
        while(lt+1<rt){
            int mid=lt+rt>>1;
            if(val[mid]>x){
                rt=mid;
            }
            else{
                lt=mid;
            }
        }
    }
    return lt;
}
set<int> st[250005];
priority_queue<int> q;
bool tag;
bool check(int X){
    while(!q.empty())q.pop();
    for(int i=1;i<=pos;i++){
        st[i].clear();
    }
    int lt=1,rt=0;
    int sum=0;
    while(rt<n){
        rt++;
        while(lt<rt&&a[rt].x-a[lt].x>X){
            st[mp[a[lt].y]].erase(a[lt].x);
            lt++;
        }
        int L=findsuf(a[rt].y-X);
        int R=findpre(a[rt].y+X);
        for(int i=L;i<=R;i++){
            for(int v:st[i]){
                if(max(abs(a[rt].y-val[i]),abs(v-a[rt].x))<=X)q.push(-max(abs(a[rt].y-val[i]),abs(v-a[rt].x))),sum++;
            }
        }
        st[mp[a[rt].y]].insert(a[rt].x);
    }
    return sum>=k;
}
signed main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &a[i].x,&a[i].y);
        int tmpx=a[i].x+a[i].y;
        int tmpy=a[i].x-a[i].y;
        a[i].x=tmpx;
        a[i].y=tmpy;
    }
    sort(a + 1, a + 1 + n, cmp2);
    pos=1;
    val[pos]=a[1].y;
    mp[a[1].y]=pos;
    for(int i=2;i<=n;i++){//
        if(a[i].y!=a[i-1].y){
            pos++;
            mp[a[i].y]=pos;
            val[pos]=a[i].y;
        }
    }
    sort(a+1,a+1+n,cmp);
    while(lt+1<rt){
        int mid=lt+rt>>1;
        if(check(mid)){
            rt=mid;
        }
        else{
            lt=mid;
        }
    }
    tag=true;
    check(rt);
    while(k--){
        printf("%lld\n",-q.top());
        q.pop();
    }
    return 0;
}