#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
/*
We transform each point (x, y) into a point (x', y') where x' = x+y and y' = x-y. The Manhattan
distance between (x1, y1) and (x2, y2) = |x1-x2| + |y1-y2| = max( |x1'-x2'|, |y1'-y2'| ).
1. Transform each point (x, y) into a point (x1, y1) where x1 = x+y and y1 = x-y. √
2. Sort the points (x1, y1) twice, once by x1 and once by y1. √
3. Iterate over points sorted by x1:
4. Maintain a set of these points sorted by the distance to the closest neighbor.
5. Repeatedly, find the smallest such distance.
6. If this distance is larger than the X-Y distance, add it to the result set.
*/
long long long_absval(long long x)
{
return max(x, -x);
}
const int maxN = 250000;
const long long INF = 1'000'000'000'000'000'000LL;
vector<long long> A(1+maxN), B(1+maxN);
vector<int> I_A, I_B;
int N, K;
struct loc
{
int i;
long long v;
};
bool operator < (loc P, loc Q)
{
if(P.v == Q.v) return P.i < Q.i;
return P.v < Q.v;
}
vector<int> nxtA, nxtB;
vector<long long> valA, valB;
void compute_score_A(int i)
{
valA[i] = INF;
if(nxtA[i] <= N-1)
{
valA[i] = A[ I_A[nxtA[i]] ] - A[ I_A[i] ];
}
}
void compute_score_B(int i)
{
valB[i] = INF;
if(nxtB[i] <= N-1)
{
valB[i] = B[ I_B[nxtB[i]] ] - B[ I_B[i] ];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for(int i = 1; i <= N; i++)
{
long long X, Y;
cin >> X >> Y;
A[i] = X+Y;
B[i] = X-Y;
}
I_A = I_B = vector<int>(N);
for(int i = 0; i < N; i++)
{
I_A[i] = i+1;
I_B[i] = i+1;
}
sort(I_A.begin(), I_A.end(), [] (int p, int q)
{
return A[p] < A[q];
});
sort(I_B.begin(), I_B.end(), [] (int p, int q)
{
return B[p] < B[q];
});
multiset<long long> res;
nxtA = vector<int>(N);
for(int i = 0; i < N; i++)
{
nxtA[i] = i+1;
}
valA = vector<long long>(N, INF);
for(int i = 0; i < N; i++)
{
compute_score_A(i);
}
set<loc> LA;
for(int i = 0; i < N; i++) LA.insert(loc{i, valA[i]});
nxtB = vector<int>(N);
for(int i = 0; i < N; i++)
{
nxtB[i] = i+1;
}
valB = vector<long long>(N, INF);
for(int i = 0; i < N; i++)
{
compute_score_B(i);
}
set<loc> LB;
for(int i = 0; i < N; i++) LB.insert(loc{i, valB[i]});
while(res.size() < K)
{
if(valA[LA.begin()->i] < valB[LB.begin()->i])
{
int i = LA.begin()->i;
LA.erase(LA.begin());
// cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';
// if(val[i] >= INF) break;
int j = nxtA[i]; //!!!!!
if(j > N-1) break;
if(long_absval(A[ I_A[i] ] - A[ I_A[j] ]) >= long_absval(B[ I_A[i] ] - B[ I_A[j] ]))
{
res.insert(long_absval(A[ I_A[i] ] - A[ I_A[j] ]));
// cerr << I_A[i] << ' ' << I_A[j] << ' ' << abs(A[ I_A[i] ] - A[ I_A[j] ]) << '\n';
}
nxtA[i]++;
compute_score_A(i);
LA.insert(loc{i, valA[i]});
}
else
{
int i = LB.begin()->i;
LB.erase(LB.begin());
int j = nxtB[i]; //!!!!!
// cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';
if(j > N-1) break;
if(long_absval(B[ I_B[i] ] - B[ I_B[j] ]) > long_absval(A[ I_B[i] ] - A[ I_B[j] ]))
{
res.insert(long_absval(B[ I_B[i] ] - B[ I_B[j] ]));
// cerr << I_B[i] << ' ' << I_B[j] << ' ' << abs(B[ I_B[i] ] - B[ I_B[j] ]) << '\n';
}
nxtB[i]++;
compute_score_B(i);
LB.insert(loc{i, valB[i]});
}
}
int ct = 0;
for(long long r:res)
{
ct++;
if(ct > K) break;
cout << r << '\n';
}
}
/* Version 1
//Part 1: iterate over I_A;
nxtA = vector<int>(N);
for(int i = 0; i < N; i++)
{
nxtA[i] = i+1;
}
valA = vector<long long>(N, INF);
for(int i = 0; i < N; i++)
{
compute_score_A(i);
}
set<loc> LA;
for(int i = 0; i < N; i++) LA.insert(loc{i, valA[i]});
++++
while(res.size() < K)
{
int i = LA.begin()->i;
LA.erase(LA.begin());
// cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';
// if(val[i] >= INF) break;
int j = nxtA[i]; //!!!!!
if(j > N-1) break;
if(long_absval(A[ I_A[i] ] - A[ I_A[j] ]) >= long_absval(B[ I_A[i] ] - B[ I_A[j] ]))
{
res.insert(long_absval(A[ I_A[i] ] - A[ I_A[j] ]));
// cerr << I_A[i] << ' ' << I_A[j] << ' ' << abs(A[ I_A[i] ] - A[ I_A[j] ]) << '\n';
}
nxtA[i]++;
compute_score_A(i);
LA.insert(loc{i, valA[i]});
}
// cerr << "switching \n";
//Part 2: iterate over I_B;
nxtB = vector<int>(N);
for(int i = 0; i < N; i++)
{
nxtB[i] = i+1;
}
valB = vector<long long>(N, INF);
for(int i = 0; i < N; i++)
{
compute_score_B(i);
}
set<loc> LB;
for(int i = 0; i < N; i++) LB.insert(loc{i, valB[i]});
++++++++++++
// cerr << "hello\n";
while(res.size() < 2*K)
{
int i = LB.begin()->i;
LB.erase(LB.begin());
int j = nxtB[i]; //!!!!!
// cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';
if(j > N-1) break;
if(long_absval(B[ I_B[i] ] - B[ I_B[j] ]) > long_absval(A[ I_B[i] ] - A[ I_B[j] ]))
{
res.insert(long_absval(B[ I_B[i] ] - B[ I_B[j] ]));
// cerr << I_B[i] << ' ' << I_B[j] << ' ' << abs(B[ I_B[i] ] - B[ I_B[j] ]) << '\n';
}
nxtB[i]++;
compute_score_B(i);
LB.insert(loc{i, valB[i]});
}
*/
