#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int64_t inf = 1e17;
class segment_tree {
private:
int n;
vector<pair<int, int>> seg;
public:
segment_tree(int n) : n(n), seg(2 * n, {-inf, -1}) {}
void set(int i, pair<int, int> x) {
for (seg[i += n] = x, i >>= 1; i > 0; i >>= 1) {
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
pair<int, int> query(int l, int r) {
pair<int, int> ans = {-inf, -1};
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ans = max(ans, seg[l++]);
if (r & 1)
ans = max(ans, seg[--r]);
}
return ans;
}
};
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
vector<int> buff;
for (auto &[x, y] : a) {
cin >> x >> y;
buff.push_back(y);
}
sort(a.begin(), a.end());
sort(buff.begin(), buff.end());
buff.erase(unique(buff.begin(), buff.end()), buff.end());
auto comp = [&](int i) { return lower_bound(buff.begin(), buff.end(), i) - buff.begin(); };
vector<vector<int>> deacti(n);
auto process = [&]() {
segment_tree st_abv(buff.size()), st_blw(buff.size());
int ans = 1e15;
int ansi = -1, ansj = -1;
vector<multiset<int>> abv_vals(buff.size()), blw_vals(buff.size());
vector<set<int>> abv_idxs(buff.size()), blw_idxs(buff.size());
vector<set<pair<int, int>>> abv_search(buff.size()), blw_search(buff.size());
for (int i = 0; i < buff.size(); ++i) {
abv_vals[i].insert(-inf);
blw_vals[i].insert(-inf);
}
auto refresh = [&](int compy) {
st_abv.set(compy, {*abv_vals[compy].rbegin(), compy});
st_blw.set(compy, {*blw_vals[compy].rbegin(), compy});
};
for (int i = 0; i < n; ++i) {
for (int &idx : deacti[i]) {
auto compy = comp(a[idx].second);
int v1 = a[idx].first + a[idx].second, v2 = a[idx].first - a[idx].second;
abv_idxs[compy].erase(idx), blw_idxs[compy].erase(idx);
abv_vals[compy].erase(abv_vals[compy].find(v1));
blw_vals[compy].erase(blw_vals[compy].find(v2));
abv_search[compy].erase({v1, idx});
blw_search[compy].erase({v2, idx});
refresh(compy);
}
int compy = comp(a[i].second);
auto [v1, compy1] = st_abv.query(0, compy);
auto [v2, compy2] = st_blw.query(compy, buff.size() - 1);
if ((a[i].first + a[i].second) - v1 < ans) {
ans = (a[i].first + a[i].second) - v1;
ansi = i, ansj = abv_search[compy1].lower_bound({v1, -1})->second;
}
if ((a[i].first - a[i].second) - v2 < ans) {
ans = (a[i].first - a[i].second) - v2;
ansi = i, ansj = blw_search[compy2].lower_bound({v2, -1})->second;
}
for (int &idx : deacti[i]) {
auto compy = comp(a[idx].second);
int v1 = a[idx].first + a[idx].second, v2 = a[idx].first - a[idx].second;
abv_idxs[compy].insert(idx), blw_idxs[compy].insert(idx);
abv_vals[compy].insert(v1);
blw_vals[compy].insert(v2);
abv_search[compy].insert({v1, idx});
blw_search[compy].insert({v2, idx});
refresh(compy);
}
int vv1 = a[i].first + a[i].second;
int vv2 = a[i].first - a[i].second;
abv_vals[compy].insert(vv1);
blw_vals[compy].insert(vv2);
abv_idxs[compy].insert(i);
blw_idxs[compy].insert(i);
abv_search[compy].insert({vv1, i});
blw_search[compy].insert({vv2, i});
refresh(compy);
}
cout << ans << endl;
// at ansi, deactivate if ansj is lesser
deacti[max(ansi, ansj)].push_back(min(ansi, ansj));
};
for (int i = 0; i < k; ++i) {
process();
}
}
