← 返回题目列表

Codeforces · 685/C

C. 最佳点

中文机器翻译题面 查看原题

当河流把格尔达带到懂得魔法的老太太家里时,这位女士决定让格尔达成为她的女儿。她希望格尔达忘记凯,所以她把花园里的所有玫瑰都放在地下。

住在这个花园里的鼹鼠现在不用上到地表就可以观赏玫瑰了。典型的痣是盲人,但这颗痣被老太太赋予了特殊的视力。他可以在任何距离观察任何地下物体,甚至可以穿过障碍物和其他物体。然而,图像的质量取决于曼哈顿到被观察物体的距离。

鼹鼠想要找到观看玫瑰的最佳点,即具有整数坐标的点,使得到玫瑰的最大曼哈顿距离尽可能小。

像往常一样,他请你帮忙。

点 (x1, y1, z1) 和 (x2, y2, z2) 之间的曼哈顿距离定义为 |x1 - x2| + |y1 - y2| + |z1 - z2|。

输入

输入的第一行包含一个整数 t t (1 ≤ t ≤ 100 000) — 测试用例的数量。然后紧跟 t 个块,每个块包含一个测试的描述。

每个块的第一行包含一个整数 ni (1 ≤ ni ≤ 100 000) – 测试中玫瑰的数量。然后遵循 ni 行,每行包含三个整数 - 相应玫瑰的坐标。请注意,两朵或更多朵玫瑰可能处于同一位置。

保证所有ni的总和不超过100 000并且所有坐标的绝对值不大于1018。

输出

对于每个 t 测试用例,打印三个整数 - 观看玫瑰的最佳点的坐标。如果有许多最佳答案,请打印其中任何一个。

最优点的坐标可能与任何玫瑰的坐标一致。

示例

输入 #1

1
5
0 0 4
0 0 -4
0 4 0
4 0 0
1 1 1

输出 #1

0 0 0

输入 #2

2
1
3 5 9
2
3 5 9
3 5 9

输出 #2

3 5 9
3 5 9

注意

在第一个样本中,从点到玫瑰的最大曼哈顿距离等于 4。

在第二个示例中,最大可能距离为 0。请注意,玫瑰的位置可能彼此重合,也可能与最优点的位置重合。