joisc-road

/*
    Normie's Template v2.1
    Changes:
    Added vectorization optimizations.
*/

// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;

// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>

// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)

//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define endl "\n"

//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))

//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}

//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;

//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>

//Quick power of 2.
#define pow2(x) (ll(1)<<x)

//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)

//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

//---------END-------//
struct FenwickTree {
    int bit[260001];  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        for (int i=0;i<n;i++) bit[i]=0;
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        l++;
        r++;
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        idx++;
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
FenwickTree fen(260000);





vector<ll> vec;
ll n,m,i,j,k,t,t1,u,v,a,b;
ll x[250001],y[250001];
vector<ll> liss,lism;
ll cur[250001];
vector<int> ev[250001][3];
vector<ll> res;

vector<int> sorts,sortm;
int ls[250001],rs[250001],lm[250001],rm[250001];
int cs[250001],cm[250001];


struct segv
{
    vector<pii(int)> cnt[1000001];
    vector<pii(int)> res;
    void reset(int c, int l, int r)
    {
        cnt[c].clear();
        if (l<r)
        {
            int mid=(l+r)/2;
            reset((c<<1),l,mid);
            reset((c<<1)+1,mid+1,r);
        }
    }
    void add(int c, int l, int r, int x, int y)
    {
        if ((l<=x)and(x<=r))
        {
            cnt[c].push_back({liss[y],lism[x]});
            if (l<r)
            {
            int mid=(l+r)/2;
            add((c<<1),l,mid,x,y);
            add((c<<1)+1,mid+1,r,x,y);
            }
        }
    }
    void get(int c, int l, int r, int tl, int tr, ll y)
    {
        if ((l>tr)or(r<tl)) return;
        if ((l>=tl)and(r<=tr))
        {
            for (int i=cnt[c].size()-1;i>=0;i--) if (cnt[c][i].fi>=y) res.push_back(cnt[c][i]);
            else break;
        }
        else
        {
            int mid=(l+r)/2;
            get((c<<1),l,mid,tl,tr,y);
            get((c<<1)+1,mid+1,r,tl,tr,y);
        }
    }
};
segv stv;




ll check(ll val)
{
    for (i=0;i<liss.size();i++) ev[i][0].clear();
    for (i=0;i<liss.size();i++) ev[i][1].clear();
    for (i=0;i<liss.size();i++) ev[i][2].clear();
    for (i=0;i<260000;i++) fen.bit[i]=0;


    a=0;
    b=0;
    for (i=1;i<=n;i++)
    {
        v=sorts[i-1];
        while (liss[a]<x[v]+y[v]-val) a++;
        while ((b<liss.size()-1)and(liss[b+1]<=x[v]+y[v]+val)) b++;
        ls[v]=a;
        rs[v]=b;
    }


    a=0;
    b=0;
    for (i=1;i<=n;i++)
    {
        v=sortm[i-1];
        while (lism[a]<x[v]-y[v]-val) a++;
        while ((b<lism.size()-1)and(lism[b+1]<=x[v]-y[v]+val)) b++;
        lm[v]=a;
        rm[v]=b;
    }

    for (i=1;i<=n;i++)
    {
        ev[cs[i]][1].push_back(i);
        ev[ls[i]][0].push_back(i);
        ev[rs[i]][2].push_back(i);
        cur[i]=0;
    }

    for (i=0;i<liss.size();i++)
    {
    //  cout<<g.p1<<' '<<g.p2<<' '<<g.p3<<endl;
        for (auto g : ev[i][0])
        {
            u=lm[g];
            v=rm[g];
    //      cout<<"ask "<<u<<' '<<v<<endl;
            a=fen.sum(u,v);
    //      cout<<a<<endl;
            cur[g]-=a;
        }
        for (auto g : ev[i][1])
        {
            u=cm[g];
            fen.add(u,1);
        }
        for (auto g : ev[i][2])
        {
            u=lm[g];
            v=rm[g];
        //  cout<<"ask "<<u<<' '<<v<<endl;
            a=fen.sum(u,v);
        //  cout<<a<<endl;
            cur[g]+=a;
        }
    }

    u=0;
    for (i=1;i<=n;i++) u+=(cur[i]-1);
    u/=2;
//  cout<<"check "<<val<<' '<<u<<endl;
    return (u<m);
}
int main()
{
//  freopen("test.txt","r",stdin);
//  freopen("testans.txt","w",stdout);
    fio;
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        liss.push_back(x[i]+y[i]);
        lism.push_back(x[i]-y[i]);
        sorts.push_back(i);
        sortm.push_back(i);
    }




    sort(liss.begin(),liss.end());
    auto its=unique(liss.begin(),liss.end());
    liss.erase(its,liss.end());
    sort(lism.begin(),lism.end());
    auto itm=unique(lism.begin(),lism.end());
    lism.erase(itm,lism.end());


    for (i=1;i<=n;i++) cs[i]=lower_bound(liss.begin(),liss.end(),x[i]+y[i])-liss.begin();
    for (i=1;i<=n;i++) cm[i]=lower_bound(lism.begin(),lism.end(),x[i]-y[i])-lism.begin();

    sort(sorts.begin(),sorts.end(),[](int a, int b){
        return (cs[a]<cs[b]);
    });

    sort(sortm.begin(),sortm.end(),[](int a, int b){
        return (cm[a]<cm[b]);
    });



//  for (auto g : liss) cout<<g<<' '; cout<<endl;
//  for (auto g : lism) cout<<g<<' '; cout<<endl;
    ll l=0,r=4e9+1,mid=0;
    while(l<r)
    {
        mid=(l+r)/2;

//      cerr<<l<<' '<<r<<' '<<mid<<endl;
        if (check(mid+1)) l=mid+1;
        else r=mid;
    }





    stv.reset(1,0,lism.size()-1);


    for (i=0;i<liss.size();i++) ev[i][0].clear();
    for (i=0;i<liss.size();i++) ev[i][1].clear();
    for (i=0;i<liss.size();i++) ev[i][2].clear();

    for (i=1;i<=n;i++)
    {

        u=lower_bound(liss.begin(),liss.end(),x[i]+y[i])-liss.begin();
        ev[u][1].push_back(i);
        u=upper_bound(liss.begin(),liss.end(),x[i]+y[i]+l)-liss.begin()-1;
        ev[u][2].push_back(i);
    }

    for (i=0;i<liss.size();i++)
    {
        for (auto g : ev[i][1])
        {
            u=lower_bound(lism.begin(),lism.end(),x[g]-y[g])-lism.begin();
            stv.add(1,0,lism.size()-1,u,i);
        }
        for (auto g : ev[i][2])
        {
            u=lower_bound(lism.begin(),lism.end(),x[g]-y[g]-l)-lism.begin();
            v=upper_bound(lism.begin(),lism.end(),x[g]-y[g]+l)-lism.begin()-1;
            stv.res.clear();
            stv.get(1,0,lism.size()-1,u,v,x[g]+y[g]-l);
            for (auto gg : stv.res) res.push_back(max(abs((ll)gg.fi-x[g]-y[g]),abs((ll)gg.se-x[g]+y[g])));
        }
    }
    sort(res.begin(),res.end());
    vector<ll> res2;
    for (auto g :res) if (g) res2.push_back(g);
    res.clear();
    for (i=0;i<res2.size();i+=2) res.push_back(res2[i]);
    while(res.size()<m) res.push_back(l+1);
    for (auto g :res) cout<<g<<endl;

}