524b6b9b912833d7ed654be821ba40eb3c97e95711e50837a566e6ca979cfc19
// https://szkopul.edu.pl/problemset/problem/V4Dd0K6T4K8AB9Nq7tQQEYTm/site/?key=statement
#include <bits/stdc++.h>
// #define GARY_DBG
#define GARY_LIB
constexpr int sizik = 1000 * 1001;
#define ar std::array
int n;
int k;
int k_end;
struct Point {
int x, y, z;
};
std::vector<Point> all_points;
std::vector<int> p_idxs;
struct Box {
int x1, y1, z1, x2, y2, z2;
};
constexpr int INF = INT32_MAX, NINF = INT32_MIN;
Box bounding_box(int start, int end) {
int x1 = INF, y1 = INF, z1 = INF, x2 = NINF, y2 = NINF, z2 = NINF;
for (int i = start; i < end; ++i) {
const auto& p = all_points[p_idxs[i]];
x1 = std::min(x1, p.x);
x2 = std::max(x2, p.x);
y1 = std::min(y1, p.y);
y2 = std::max(y2, p.y);
z1 = std::min(z1, p.z);
z2 = std::max(z2, p.z);
}
return {x1, y1, z1, x2, y2, z2};
}
bool found = false;
void print_ans_range(int start, int end) {
auto B = bounding_box(start, end);
std::cout << B.x1 << " " << B.y1 << " " << B.z1 << " " << B.x2 << " " << B.y2 << " " << B.z2 << '\n';
}
bool check_window(int w_start, int w_end, int scope_l, int scope_r) {
auto B = bounding_box(w_start, w_end);
int w = 0;
for (int i = scope_l; i < scope_r; ++i) {
const auto& p = all_points[p_idxs[i]];
if (B.x1 <= p.x && p.x <= B.x2 && B.y1 <= p.y && p.y <= B.y2 && B.z1 <= p.z && p.z <= B.z2) {
w++;
}
if (w > k_end) return false;
}
return k <= w && w <= k_end;
}
bool Rozwiaz(int L, int R) {
if (found) return true;
int sz = R - L;
if (k <= sz && sz <= k_end) {
print_ans_range(L, R);
return found = true;
}
if (sz < k) {
return false;
}
int min_v[3] = {(int)INF, (int)INF, (int)INF};
int max_v[3] = {(int)NINF, (int)NINF, (int)NINF};
for (int i = L; i < R; ++i) {
const auto& p = all_points[p_idxs[i]];
min_v[0] = std::min(min_v[0], (int)p.x);
max_v[0] = std::max(max_v[0], (int)p.x);
min_v[1] = std::min(min_v[1], (int)p.y);
max_v[1] = std::max(max_v[1], (int)p.y);
min_v[2] = std::min(min_v[2], (int)p.z);
max_v[2] = std::max(max_v[2], (int)p.z);
}
int diff[3];
diff[0] = max_v[0] - min_v[0];
diff[1] = max_v[1] - min_v[1];
diff[2] = max_v[2] - min_v[2];
int ax = 0;
if (diff[1] > diff[0]) ax = 1;
if (diff[2] > diff[ax]) ax = 2;
if (diff[ax] == 0) {
print_ans_range(L, L + k);
return found = true;
}
std::sort(p_idxs.begin() + L, p_idxs.begin() + R, [ax](int a, int b) {
if (ax == 0) return all_points[a].x < all_points[b].x;
if (ax == 1) return all_points[a].y < all_points[b].y;
return all_points[a].z < all_points[b].z;
});
if (check_window(L, L + k, L, R)) {
print_ans_range(L, L + k);
return found = true;
}
if (check_window(R - k, R, L, R)) {
print_ans_range(R - k, R);
return found = true;
}
int mid_offset = sz / 2;
int abs_mid = L + mid_offset;
while (abs_mid + 1 < R) {
int val1, val2;
int idx1 = p_idxs[abs_mid];
int idx2 = p_idxs[abs_mid + 1];
if (ax == 0) {
val1 = all_points[idx1].x;
val2 = all_points[idx2].x;
} else if (ax == 1) {
val1 = all_points[idx1].y;
val2 = all_points[idx2].y;
} else {
val1 = all_points[idx1].z;
val2 = all_points[idx2].z;
}
if (val1 == val2)
abs_mid++;
else
break;
}
if (abs_mid == R - 1) {
abs_mid = L + mid_offset;
while (abs_mid > L) {
int val1, val2;
int idx1 = p_idxs[abs_mid - 1];
int idx2 = p_idxs[abs_mid];
if (ax == 0) {
val1 = all_points[idx1].x;
val2 = all_points[idx2].x;
} else if (ax == 1) {
val1 = all_points[idx1].y;
val2 = all_points[idx2].y;
} else {
val1 = all_points[idx1].z;
val2 = all_points[idx2].z;
}
if (val1 == val2)
abs_mid--;
else {
abs_mid--;
break;
}
}
}
int left_sz = (abs_mid + 1) - L;
int right_sz = R - (abs_mid + 1);
if (left_sz == 0 || right_sz == 0) return false;
if (left_sz >= k) {
if (Rozwiaz(L, abs_mid + 1)) return found = true;
}
if (right_sz >= k) {
if (Rozwiaz(abs_mid + 1, R)) return found = true;
}
return false;
}
void solve() {
std::cin >> n >> k;
k_end = (3 * k) / 2;
all_points.resize(n);
p_idxs.resize(n);
for (int i = 0; i < n; i++) {
std::cin >> all_points[i].x >> all_points[i].y >> all_points[i].z;
p_idxs[i] = i;
}
if (n <= 10) {
for (int q = 1; q < (1 << n); ++q) {
int x1 = INF, y1 = INF, z1 = INF;
int x2 = NINF, y2 = NINF, z2 = NINF;
bool any = false;
for (int i = 0; i < n; ++i) {
if ((q >> i) & 1) {
any = true;
x1 = std::min(x1, all_points[i].x);
x2 = std::max(x2, all_points[i].x);
y1 = std::min(y1, all_points[i].y);
y2 = std::max(y2, all_points[i].y);
z1 = std::min(z1, all_points[i].z);
z2 = std::max(z2, all_points[i].z);
}
}
if (!any) continue;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (all_points[i].x >= x1 && all_points[i].x <= x2 && all_points[i].y >= y1 && all_points[i].y <= y2 && all_points[i].z >= z1 &&
all_points[i].z <= z2) {
cnt++;
}
}
if (cnt >= k && cnt <= k_end) {
std::cout << x1 << " " << y1 << " " << z1 << " " << x2 << " " << y2 << " " << z2 << "\n";
return;
}
}
return;
}
found = false;
Rozwiaz(0, n);
}
int32_t main() {
#ifndef GARY_DBG
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
#endif
all_points.reserve(500000);
p_idxs.reserve(500000);
int t = 1;
std::cin >> t;
for (; t > 0; t--) {
solve();
}
return 0;
}