OI XXXII - ogr (Pb0207)

// https://szkopul.edu.pl/problemset/problem/V4Dd0K6T4K8AB9Nq7tQQEYTm/site/?key=statement

// author: pb0207

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 1e3 + 7;

int T, n, k, L, R;

struct P {
    int x[3];
};

int solve(vector<P> v, int d) {
    if (v.size() < k) return 0;

    if (d == 3) return 0;

    map<int, vector<P>> pts;

    for (auto u : v)
        pts[u.x[d]].push_back(u);

    int sum = 0;

    for (auto it = pts.begin(), jt = pts.begin(); it != pts.end(); it++) {
        sum += it->second.size();

        while (sum > R && jt != it) {
            sum -= jt->second.size();
            jt++;
        }

        if (sum >= L && sum <= R) {
            vector<int> ans(6);

            for (int i = 0; i < 3; i++) {
                if (i != d) {
                    ans[i] = 1e9;
                    ans[i + 3] = 0;

                    for (auto u : v)
                        ans[i] = min(ans[i], u.x[i]), ans[i + 3] = max(ans[i + 3], u.x[i]);
                } else
                    ans[i] = jt->first, ans[i + 3] = it->first;
            }

            for (int i = 0; i < 6; i++)
                cout << ans[i] << " \n"[i + 1 == 6];

            return 1;
        }
    }

    for (auto [x, y] : pts)
        if (solve(y, d + 1)) return 1;

    for (auto it = pts.begin(), jt = next(pts.begin()); jt != pts.end(); it++, jt++) {
        auto nxv = it->second;
        nxv.insert(nxv.end(), jt->second.begin(), jt->second.end());

        if (solve(nxv, d + 1)) return 1;
    }

    return 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;

    while (T--) {
        cin >> n >> k;
        L = k, R = (3 * k + 1) / 2;
        vector<P> v(n);

        for (auto& u : v)
            cin >> u.x[0] >> u.x[1] >> u.x[2];

        assert(solve(v, 0));
    }
}