#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int N = 250500;
const int OFF = (1 << 20);
int T[3 * N];
int n, q, po_X[N], po_Y[N];
int ind[3 * N], izb[N];
vector < int > TT[2 * OFF];
ll x[N], y[N];
void update(int lo, int hi, int x){
hi += 11, lo += 10;
for(; hi < 3 * N; hi += hi & -hi)
T[hi] -= x;
for(; lo < 3 * N ; lo += lo & -lo)
T[lo] += x;
}
int query(int x){
int ret = 0;
x += 10;
for(; x ; x -= x & -x)
ret += T[x];
return ret;
}
void update2(int i, int a, int b, int lo, int hi, int x){
if(lo <= a && b <= hi) {
TT[i].PB(x);
return;
}
if(a > hi || b < lo) return;
update2(2 * i, a, (a + b) / 2, lo, hi, x);
update2(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}
vector < int > ret;
void query2(int x){
ret.clear();
for(x = (x + OFF); x ; x /= 2){
vector < int > nw;
for(int y : TT[x])
if(!izb[y])
ret.PB(y), nw.PB(y);
TT[x] = nw;
}
}
vector < pii > swp;
ll labs(ll x){
return x > 0 ? x : -x;
}
ll get_dis(int i, int j){
return max(labs(x[i] - x[j]), labs(y[i] - y[j]));
}
bool cmpX(int A, int B){
return x[A] < x[B];
}
bool cmpY(int A, int B){
return y[A] < y[B];
}
ll prebroji(ll k){
swp.clear();
memset(T, 0, sizeof(T));
int A = 0, B = 0, C = 0;
for(;A < n || B < n || C < n;){
if(A < n && (B == n || x[po_X[A]] - k <= x[po_X[B]]) && (C == n || x[po_X[A]] - k <= x[po_X[C]] + k))
swp.PB({0, po_X[A]}), A++;
else if(B < n && (A == n || x[po_X[B]] < x[po_X[A]] - k) && (C == n || x[po_X[B]] <= x[po_X[C]] + k))
swp.PB({1, po_X[B]}), B++;
else
swp.PB({2, po_X[C]}), C++;
}
A = 0, B = 0, C = 0; int siz = 0;
for(;A < n || B < n || C < n;){
if(A < n && (B == n || y[po_Y[A]] - k <= y[po_Y[B]]) && (C == n || y[po_Y[A]] - k <= y[po_Y[C]] + k))
ind[3 * po_Y[A]] = siz++, A++;
else if(B < n && (A == n || y[po_Y[B]] < y[po_Y[A]] - k) && (C == n || y[po_Y[B]] <= y[po_Y[C]] + k))
ind[3 * po_Y[B] + 1] = siz++, B++;
else
ind[3 * po_Y[C] + 2] = siz++, C++;
}
ll ret = 0;
for(pair < int , int > tmp : swp){
if(tmp.X == 0)
update(ind[3 * tmp.Y], ind[3 * tmp.Y + 2], 1);
else if(tmp.X == 1)
ret += query(ind[3 * tmp.Y + 1]);
else
update(ind[3 * tmp.Y], ind[3 * tmp.Y + 2], -1);
}
ret = (ret - n) / 2LL;
return ret;
}
vector < ll > pot;
void pronadi(ll k){
swp.clear();
memset(izb, 0, sizeof(izb));
int A = 0, B = 0, C = 0;
for(;A < n || B < n || C < n;){
if(A < n && (B == n || x[po_X[A]] - k <= x[po_X[B]]) && (C == n || x[po_X[A]] - k <= x[po_X[C]] + k))
swp.PB({0, po_X[A]}), A++;
else if(B < n && (A == n || x[po_X[B]] < x[po_X[A]] - k) && (C == n || x[po_X[B]] <= x[po_X[C]] + k))
swp.PB({1, po_X[B]}), B++;
else
swp.PB({2, po_X[C]}), C++;
}
A = 0, B = 0, C = 0; int siz = 0;
for(;A < n || B < n || C < n;){
if(A < n && (B == n || y[po_Y[A]] - k <= y[po_Y[B]]) && (C == n || y[po_Y[A]] - k <= y[po_Y[C]] + k))
ind[3 * po_Y[A]] = siz++, A++;
else if(B < n && (A == n || y[po_Y[B]] < y[po_Y[A]] - k) && (C == n || y[po_Y[B]] <= y[po_Y[C]] + k))
ind[3 * po_Y[B] + 1] = siz++, B++;
else
ind[3 * po_Y[C] + 2] = siz++, C++;
}
for(pair < int , int > tmp : swp){
if(tmp.X == 0)
update2(1, 0, OFF - 1, ind[3 * tmp.Y], ind[3 * tmp.Y + 2], tmp.Y);
else if(tmp.X == 1){
query2(ind[3 * tmp.Y + 1]);
for(int y : ret)
if(y < tmp.Y)
pot.PB(get_dis(y, tmp.Y));
}
else
izb[tmp.Y] = 1;
}
}
int main(){
scanf("%d%d", &n, &q);
for(int i = 0;i < n;i++){
int tx, ty; scanf("%d%d", &tx, &ty);
x[i] = tx + ty, y[i] = tx - ty;
po_X[i] = i, po_Y[i] = i;
}
sort(po_X, po_X + n, cmpX);
sort(po_Y, po_Y + n, cmpY);
ll mks = 0;
for(int i = 32;i >= 0;i--)
if(prebroji(mks + (1LL << i)) < q)
mks += (1LL << i);
pronadi(mks); sort(pot.begin(), pot.end());
for(ll x : pot)
printf("%lld\n", x);
for(int i = 0;i < q - (int)pot.size();i++)
printf("%lld\n", mks + 1);
return 0;
}
