2018 程序设计基础期末上机考试

F. 奇怪的中心点

单点时限: 2.0 sec

内存限制: 256 MB

计算 $n$ 个三维坐标点 $(x_1,y_1,z_1),\ldots,(x_n,y_n,z_n)$ 的中心点 $C$。

中心点 $C$ 按如下定义:中心点 $C(x,y,z)$ 满足 $x,y,z$ 都是整数,且与每个点之间的距离之和 $$\sum_{i=1}^n \sqrt{(x-x_i)^2+(y-y_i)^2+(z-z_i)^2}$$ 最小。

说明:计算求到的中心点 $C$ 可能不唯一,若有多个中心点,返回坐标值 $x$ 最小的那个中心点;若几个中心点的 $x$ 坐标也相同,返回坐标值 $y$ 最小的那个中心点;若几个中心点的 $x,y$ 坐标也相同,返回 $z$ 坐标最小的中心点。

输入格式

第 1 行:输入一个正整数 $n$ ($2 \le n \le 100$),$n$ 表示点的个数。

接下来 $n$ 行:每行输入三个整数 $x,y,z$,表示点的三维坐标值,$-50 \le x,y,z \le 50$,整数之间用一个空格分隔。可能会有重复的点。

输出格式

输出中心点 $C$ 的三维坐标 $x,y,z$,整数之间用空格分隔。

样例

Input
4
3 1 4
1 5 9
2 6 5
3 5 9
Output
2 5 8