#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> 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<pair<int, int>, int>> cdombi(vector<pair<pair<int, int>, int>>& a, vector<pair<pair<int, int>, int>>& b) { if (max(a[0].second, a[1].second) > max(b[0].second, b[1].second)) return b; return a; } 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]; if (r - l == 1) { getans[0] = { {an[0].first, an[0].second}, 1 }; getans[1] = { {md1 + 5, md1 + 5}, 1 }; return true; } for (int II = 0; II < 2; II++) { 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] = { {an[i - 1].first - k, mn}, max(1, max(an[i - 1].first - an[0].first, mx - mn)) }; getans[1] = { {an[i].first, sn[i]}, k }; if (!II) { if (an[i].first - 2 - bou < k) continue; getans[0].first.first = min(an[0].first, an[i].first - 1 - k); } if (II) { swap(getans[0].first.first, getans[0].first.second); swap(getans[1].first.first, getans[1].first.second); } return true; } mn = min(mn, an[i].second); mx = max(mx, an[i].second); } for (int i = 0; i < r - l; i++) swap(an[i].first, an[i].second); sort(an.begin(), an.end()); } return false; } int 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, -md1 * 2 - 1)) { 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 <= k && yx - yn <= k) { 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--; if (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; }