#include <iostream> #include <string> #include <algorithm> #include <iomanip> #include <vector> #include <map> #include <iterator> #include <set> #include <random> #include <unordered_map> #include <queue> #include <cassert> #include <stack> #include <numeric> #include <deque> #define int long long using namespace std; typedef long long ll; typedef long double ld; const ll md1 = 1'000'000'000; const ll md2 = 998244353; const ll mdd = 666013; vector<pair<int, int>> a; vector<pair<pair<int, int>, int>> getans; bool check2(int l, int r, int k, int bou) { vector<pair<int, int>> an(r - l); for (int i = l; i < r; i++) an[i - l] = { a[i].second, a[i].first }; sort(an.begin(), an.end()); if (r - l == 1) { getans[0] = { {an[0].second, an[0].first}, 1 }; getans[1] = { {md1 + 5, md1 + 5}, 1 }; return true; } vector<int> sx(r - l), sn(r - l); sx[r - l - 1] = an[r - l - 1].second; sn[r - l - 1] = an[r - l - 1].second; for (int i = r - l - 2; i > -1; i--) { sn[i] = min(sn[i + 1], an[i].second); sx[i] = max(sx[i + 1], an[i].second); } int mn = an[0].second; int mx = an[0].second; for (int i = 1; i < r - l; i++) { if (an[i - 1].first != an[i].first && an[i - 1].first - an[0].first <= k && mx - mn <= k && an[r - l - 1].first - an[i].first <= k && sx[i] - sn[i] <= k) { getans[0] = { { mn, an[i - 1].first - k }, k }; getans[1] = { { sn[i], an[i].first }, k }; return true; } mn = min(mn, an[i].second); mx = max(mx, an[i].second); } if (mx - mn <= k && an[r - l - 1].first - an[0].first <= k) { getans[0] = { {mn, an[0].first }, k }; getans[1] = { { md1 + 5, md1 + 5}, 1 }; return true; } sx[r - l - 1] = a[r - 1].second; sn[r - l - 1] = a[r - 1].second; for (int i = r - l - 2; i > -1; i--) { sn[i] = min(sn[i + 1], a[i + l].second); sx[i] = max(sx[i + 1], a[i + l].second); } mn = a[l].second; mx = a[l].second; for (int i = l + 1; i < r; i++) { if (a[i - 1].first != a[i].first && a[i - 1].first - a[l].first <= k && mx - mn <= k && a[r - 1].first - a[i].first <= k && sx[i - l] - sn[i - l] <= k) { int vvv = max(mx - mn, a[i - 1].first - a[l].first); if (a[i].first - 2 - bou >= vvv) { getans[0] = { { a[i].first, sn[i - l] }, k}; getans[1] = { { min(a[i].first - 1 - vvv, a[l].first), mn }, vvv}; return true; } } mn = min(mn, a[i].second); mx = max(mx, a[i].second); } return false; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { int n, k; cin >> n >> k; a.resize(n); getans.resize(k); for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second; vector<int> xa(k, md1 + 1), ya(k, md1 + 1), l(k, 1); int ans = md1 * 2; l[0] = ans; xa[0] = -md1; ya[0] = -md1; for (int i = 1; i < k; i++) xa[i] = md1 + i * 2, ya[i] = md1 + 2 * i; for (int II = 0; II < 4; II++) { sort(a.begin(), a.end()); vector<pair<pair<int, int>, int>> sufk1(n); sufk1[n - 1] = { {a[n - 1].first, a[n - 1].second }, 1 }; { int mx = a[n - 1].first, nx = a[n - 1].first, my = a[n - 1].second, ny = a[n - 1].second; for (int i = n - 2; i > -1; i--) { mx = max(mx, a[i].first); nx = min(nx, a[i].first); my = max(my, a[i].second); ny = min(ny, a[i].second); sufk1[i] = { {nx, ny}, max(mx - nx, my - ny) }; } } if (ans > sufk1[0].second) { ans = sufk1[0].second; l[0] = sufk1[0].second; xa[0] = sufk1[0].first.first; ya[0] = sufk1[0].first.second; for (int i = 1; i < k; i++) l[i] = 1, xa[i] = md1 + 2 * i, ya[i] = md1 + 2 * i; } if (k >= 2) { int ll = 0; int rr = ans; vector<pair<pair<int, int>, int>> anss(k); for (int i = 0; i < k; i++) anss[i] = { {xa[i], ya[i]}, l[i] }; while (ll + 1 < rr) { int md = (ll + rr) / 2; bool ok = false; if (k == 2) { if (check2(0, n, md, -4 * md1)) { ok = true; anss[0] = getans[0]; anss[1] = getans[1]; } } else { int xn = a[0].first, xx = a[0].first, yn = a[0].second, yx = a[0].second; int po = 0; while (po < n && xx - xn <= md && yx - yn <= md) { xn = min(xn, a[po].first); xx = max(xx, a[po].first); yn = min(yn, a[po].second); yx = max(yx, a[po].second); po++; } po--; while (po >= 1 && a[po].first == a[po - 1].first) po--; if (po && check2(po, n, md, a[po - 1].first)) { ok = true; anss[0] = getans[0]; anss[1] = getans[1]; anss[2] = { { xn, yn}, md }; } } if (ok) rr = md; else ll = md; } if (rr < ans) for (int i = 0; i < k; i++) { ans = rr; l[i] = anss[i].second; xa[i] = anss[i].first.first; ya[i] = anss[i].first.second; } } for (int i = 0; i < n; i++) a[i] = { a[i].second, -a[i].first }; for (int i = 0; i < k; i++) { int tp = xa[i] + l[i]; xa[i] = ya[i]; ya[i] = -tp; } } for (int i = 0; i < k; i++) cout << xa[i] << " " << ya[i] << " " << l[i] << "\n"; } return 0; }