#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
const ll INF = 1'000'000'000'000LL;
const int mx = 250'000;
ll X[1+mx], Y[1+mx];
struct segtree
{
int l;
int r;
pair<ll, int> mn;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
mn = {INF, l};
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
segtree(int L, int R, pair<ll, int> MN, segtree* LF, segtree* RG)
{
l = L;
r = R;
mn = MN;
left = LF;
right = RG;
}
segtree* set_value(int I, ll V)
{
if(l == r)
{
return new segtree(l, r, {V, I}, left, right);
}
else if(I <= (l+r)/2)
{
segtree* new_left = left->set_value(I, V);
return new segtree(l, r, min(new_left->mn, right->mn), new_left, right);
}
else
{
segtree* new_right = right->set_value(I, V);
return new segtree(l, r, min(left->mn, new_right->mn), left, new_right);
}
}
pair<ll, int> rangemin(int L, int R)
{
if(R < l || r < L || R < L) return {2*INF, -1};
else if(L <= l && r <= R) return mn;
else return min(left->rangemin(L, R), right->rangemin(L, R));
}
};
int N, K;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
vector<pii> P(N);
for(int i = 0; i < N; i++) cin >> P[i].first >> P[i].second;
sort(P.begin(), P.end());
for(int i = 1; i <= N; i++)
{
X[i] = P[i-1].first;
Y[i] = P[i-1].second;
}
vector<int> I(N);
for(int i = 0; i < N; i++) I[i] = i+1;
sort(I.begin(), I.end(), [] (int p, int q)
{
return Y[p] < Y[q];
});
segtree* S1[1+N]; //segtree over X, sweep line over Y
segtree* S2[1+N];
// S1[0] = new segtree(1, N);
// S2[0] = new segtree(1, N);
S1[I[0]] = new segtree(1, N);
S2[I[0]] = new segtree(1, N);
for(int j = 1; j < N; j++)
{
int i = I[j];
int i2 = I[j-1];
S1[i] = S1[i2]->set_value(i2, -X[i2] - Y[i2]);
S2[i] = S2[i2]->set_value(i2, +X[i2] - Y[i2]);
}
set< pair<ll, int> > tbv;
for(int i = 1; i <= N; i++)
{
tbv.insert({X[i] + Y[i] + S1[i]->rangemin(1, i-1).first, i});
tbv.insert({-X[i] + Y[i] + S2[i]->rangemin(i+1, N).first, -i});
}
vector<ll> res;
// cerr << "reordered points: \n";
// for(int i = 1; i <= N; i++) cerr << X[i] << ' ' << Y[i] << '\n';
for(int j = 1; j <= K; j++)
{
auto u = *tbv.begin();
tbv.erase(u);
ll v = u.first;
int i = u.second;
// cerr << "j = " << j << "\n";
// cerr << "best up point: " << i << ' ' << v << '\n';
res.push_back(v);
if(i > 0)
{
// cerr << "segtree = ";
// for(int q = 1; q <= N; q++) cerr << S1[i]->rangemin(q, q).first << "/" << S1[i]->rangemin(q,q).second << ' ';
// cerr << '\n';
// auto f = S1[i].rangemin(1, i-1);
S1[i] = S1[i]->set_value(S1[i]->rangemin(1, i-1).second, +INF);
tbv.insert({X[i] + Y[i] + S1[i]->rangemin(1, i-1).first, i});
}
else
{
S2[-i] = S2[-i]->set_value(S2[-i]->rangemin((-i)+1, N).second, +INF);
tbv.insert({-X[-i] + Y[-i] + S2[-i]->rangemin((-i)+1, N).first, i});
}
}
for(ll r: res) cout << r << '\n';
}
