#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];
multiset<int> q;
bool tag;
class BIT{
    public:
    int c[250005];
    int lowbit(int x){
        return x&-x;
    }
    void add(int x,int y){
        while(x<=pos){
            c[x]+=y;
            x+=lowbit(x);
        }
        return;
    }
    int ask(int x){
        int sum=0;
        while(x){
            sum+=c[x];
            x-=lowbit(x);
        }
        return sum;
    }
    int query(int x,int y){
        return ask(y)-ask(x-1);
    }
    void clean(){
        for(int i=1;i<=pos;i++){
            c[i]=0;
        }
        return;
    }
}P;
bool check(int X){
    P.clean();
    int sum=0;
    int lt=1,rt=0;
    while(rt<n){
        rt++;
        while(lt<rt&&a[rt].x-a[lt].x>X){
            P.add(mp[a[lt].y],-1);
            lt++;
        }
        int L=findsuf(a[rt].y-X);
        int R=findpre(a[rt].y+X);
        sum+=P.query(L,R);
        P.add(mp[a[rt].y],1);
    }
    return sum>=k;
}
bool getans(int X){
    q.clear();
    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);
        // if(tag)printf("%lld %lld %lld %lld %lld %lld\n",lt,rt,a[rt].x,a[rt].y,L,R);
        for(int i=L;i<=R;i++){
            // if(i==mp[a[rt].y])continue;
            // if(tag)printf("%lld %lu\n",i,st[i].size());
            for(int v:st[i]){
                // if(tag)printf("%lld %lld %lld %lld %lld\n",v,val[i],a[rt].x,a[rt].y,max(abs(a[rt].y-val[i]),abs(v-a[rt].x)));
                if(max(abs(a[rt].y-val[i]),abs(v-a[rt].x))<=X){
                    q.insert(max(abs(a[rt].y-val[i]),abs(v-a[rt].x))),sum++;
                    if(q.size()>k){
                        q.erase(q.begin(),q.begin());
                    }
                }
            }
        }
        st[mp[a[rt].y]].insert(a[rt].x);
        // printf("%lld?\n",sum);
    }
    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;
        // a[i].x+=2000000001;
        // a[i].y+=2000000001;
    }
    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);
    // puts("");
    // for(int i=1;i<=n;i++){
    //     printf("%lld %lld\n",a[i].x,a[i].y);
    // }
    // return 0;
    int lt=0,rt=4000000000+1;
    while(lt+1<rt){
        // printf("%lld %lld\n",lt,rt);
        int mid=lt+rt>>1;
        if(check(mid)){
            rt=mid;
        }
        else{
            lt=mid;
        }
    }
    // printf("%lld\n",rt);
    tag=true;
    // return 0;
    getans(rt);
    for(int v:q){
        printf("%lld\n",v);
        k--;
        if(!k)break;
    }
    return 0;
}
/*
把曼哈顿距离换成切比雪夫距离，然后二分第k短的路径长度，然后把x按死，通过尺取法找到区间，问题就是要找到与y距离不超过k的点的数量

5 4
1 -1
2 0
-1 0
0 2
0 -2

-9 3 -1 -3 8
-1 15 0 12 3
-1 -3 1 3 6
0 12 2 18 6
-1 15 2 18 3
-1 -3 6 -2 7
-9 3 6 -2 15
1 3 6 -2 5
-9 3 7 9 16
1 3 7 9 6
0 12 7 9 7
-1 15 7 9 8
-9 3 9 5 18
1 3 9 5 8
7 9 9 5 4

-9 3
-2 -14
-1 -3
-1 15
0 12
1 3
2 18
6 -2
7 9
9 5

-2 2
-1 -1
0 2
2 -2
2 2

-2 2 -1 -1 3
-1 -1 0 2 3
-1 -1 2 -2 3
-1 -1 2 2 3
*/

不知道怎么卡了，nlognlogn嗯过不去