242806ef099cf12107902b6da3ffcb68123dc262d5cc49eecdc2c6b61142910b
// https://szkopul.edu.pl/problemset/problem/V4Dd0K6T4K8AB9Nq7tQQEYTm/site/?key=statement
#include <bits/stdc++.h>
struct Point {
int id;
long long x, y, z;
};
struct Box {
long long x1, y1, z1, x2, y2, z2;
};
int n_in;
long long k_limit;
std::vector<Point> planets;
bool found;
Box solution;
Box get_bbox(const std::vector<int>& idxs) {
long long min_x = 2000000000LL, max_x = -1;
long long min_y = 2000000000LL, max_y = -1;
long long min_z = 2000000000LL, max_z = -1;
for (int i : idxs) {
min_x = std::min(min_x, planets[i].x);
max_x = std::max(max_x, planets[i].x);
min_y = std::min(min_y, planets[i].y);
max_y = std::max(max_y, planets[i].y);
min_z = std::min(min_z, planets[i].z);
max_z = std::max(max_z, planets[i].z);
}
return {min_x, min_y, min_z, max_x, max_y, max_z};
}
void check_window(const std::vector<int>& p, int axis) {
if (found) return;
int sz = p.size();
if (sz < k_limit) return;
long long target_max = floor(1.5 * k_limit);
auto get_val = [&](int i) {
if (axis == 0) return planets[p[i]].x;
if (axis == 1) return planets[p[i]].y;
return planets[p[i]].z;
};
long long v_start = get_val(0);
long long v_end_nominal = get_val(k_limit - 1);
int real_count = 0;
for (int i = 0; i < sz; ++i) {
long long v = get_val(i);
if (v >= v_start && v <= v_end_nominal)
real_count++;
else if (v > v_end_nominal)
break;
}
if (real_count >= k_limit && real_count <= target_max) {
std::vector<int> subset;
for (int i = 0; i < sz; ++i) {
long long v = get_val(i);
if (v >= v_start && v <= v_end_nominal) subset.push_back(p[i]);
}
solution = get_bbox(subset);
found = true;
return;
}
v_start = get_val(sz - k_limit);
long long v_end = get_val(sz - 1);
real_count = 0;
for (int i = sz - 1; i >= 0; --i) {
long long v = get_val(i);
if (v >= v_start && v <= v_end)
real_count++;
else if (v < v_start)
break;
}
if (real_count >= k_limit && real_count <= target_max) {
std::vector<int> subset;
for (int i = 0; i < sz; ++i) {
long long v = get_val(i);
if (v >= v_start && v <= v_end) subset.push_back(p[i]);
}
solution = get_bbox(subset);
found = true;
return;
}
}
void solve_recursive(std::vector<int>& p) {
if (found) return;
int n = p.size();
long long target_max = floor(1.5 * k_limit);
if (n <= target_max) {
solution = get_bbox(p);
found = true;
return;
}
long long mins[3] = {(long long)4e18, (long long)4e18, (long long)4e18};
long long maxs[3] = {-(long long)4e18, -(long long)4e18, -(long long)4e18};
for (int idx : p) {
mins[0] = std::min(mins[0], planets[idx].x);
maxs[0] = std::max(maxs[0], planets[idx].x);
mins[1] = std::min(mins[1], planets[idx].y);
maxs[1] = std::max(maxs[1], planets[idx].y);
mins[2] = std::min(mins[2], planets[idx].z);
maxs[2] = std::max(maxs[2], planets[idx].z);
}
long long spreads[3];
spreads[0] = maxs[0] - mins[0];
spreads[1] = maxs[1] - mins[1];
spreads[2] = maxs[2] - mins[2];
std::vector<int> axes = {0, 1, 2};
sort(axes.begin(), axes.end(), [&](int a, int b) { return spreads[a] > spreads[b]; });
bool split_done = false;
for (int ax : axes) {
if (found) return;
if (spreads[ax] == 0) continue;
std::sort(p.begin(), p.end(), [&](int a, int b) {
if (ax == 0) return planets[a].x < planets[b].x;
if (ax == 1) return planets[a].y < planets[b].y;
return planets[a].z < planets[b].z;
});
int mid = n / 2;
int split_idx = -1;
for (int d = 0; d < n; ++d) {
int i = mid + d;
if (i < n - 1) {
long long v1 = (ax == 0 ? planets[p[i]].x : (ax == 1 ? planets[p[i]].y : planets[p[i]].z));
long long v2 = (ax == 0 ? planets[p[i + 1]].x : (ax == 1 ? planets[p[i + 1]].y : planets[p[i + 1]].z));
if (v1 < v2) {
if ((i + 1) >= k_limit || (n - 1 - i) >= k_limit) {
split_idx = i;
break;
}
}
}
int j = mid - d - 1;
if (j >= 0) {
long long v1 = (ax == 0 ? planets[p[j]].x : (ax == 1 ? planets[p[j]].y : planets[p[j]].z));
long long v2 = (ax == 0 ? planets[p[j + 1]].x : (ax == 1 ? planets[p[j + 1]].y : planets[p[j + 1]].z));
if (v1 < v2) {
if ((j + 1) >= k_limit || (n - 1 - j) >= k_limit) {
split_idx = j;
break;
}
}
}
}
if (split_idx != -1) {
std::vector<int> L(p.begin(), p.begin() + split_idx + 1);
std::vector<int> R(p.begin() + split_idx + 1, p.end());
if (L.size() >= k_limit) solve_recursive(L);
if (found) return;
if (R.size() >= k_limit) solve_recursive(R);
if (found) return;
split_done = true;
return;
}
}
if (!split_done) {
for (int ax = 0; ax < 3; ++ax) {
std::sort(p.begin(), p.end(), [&](int a, int b) {
if (ax == 0) return planets[a].x < planets[b].x;
if (ax == 1) return planets[a].y < planets[b].y;
return planets[a].z < planets[b].z;
});
check_window(p, ax);
if (found) return;
}
}
}
void solve() {
int n;
std::cin >> n;
std::cin >> k_limit;
planets.resize(n);
std::vector<int> idxs(n);
for (int i = 0; i < n; ++i) {
std::cin >> planets[i].x >> planets[i].y >> planets[i].z;
planets[i].id = i;
idxs[i] = i;
}
found = false;
solve_recursive(idxs);
if (found) {
std::cout << solution.x1 << " " << solution.y1 << " " << solution.z1 << " " << solution.x2 << " " << solution.y2 << " " << solution.z2
<< "\n";
} else {
std::cout << "-1\n";
}
}
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t;
std::cin >> t;
for (; t > 0; t--) {
solve();
}
return 0;
}