问题描述

戈雷利安人使用空间跃迁通道在宇宙中旅行。通过跃迁通道的旅行是瞬间完成的，但出于安全考虑，一个人每$10$小时只能进行一次跃迁。此外，创建跃迁通道的成本与通道两端点之间的直线距离成正比。

作为已知宇宙中的统治力量，戈雷利安人常常感到无聊，因此他们经常以以下方式征服新的太空区域：

$1）$初始入侵：初始入侵部队找到一个合适的星球并征服它，建立一个区域戈雷利安银河政府（$Regional Gorelian Galactic Government$，简称$RGGG$），该政府将管理这个太空区域内的所有戈雷利安事务。

$2)$首次扩张：当征服下一个星球时，会在新星球与$RGGG$所在星球之间建造一条跃迁通道。通过这种方式连接的星球被称为区域戈雷利安行星网络（$Regional Gorelian Planetary Network$，简称$RGPN$）的一部分。

$3)$后续扩张：随着更多星球被征服，每个新星球都会通过一条跃迁通道与$RGPN$中已有的最近星球相连，从而将连接新星球的成本降至最低。如果有两个或多个星球与新星球距离相等，则新星球将连接到最先被征服的那个星球。

然而，这会引发一个问题。由于星球是以大致随机的方式被征服的，一段时间后，$RGGG$可能不会位于理想位置。一些需要与$RGGG$协商的戈雷利安人可能只需要进行一两次跃迁，但另一些人可能需要进行数十次——考虑到两次跃迁之间的$10$小时等待期，这非常不便。

因此，每年戈雷利安人都会对$RGPN$进行一次分析，并将$RGGG$重新定位到一个最佳位置。最佳位置被定义为一个星球，该星球能使从$RGPN$中任何星球到达$RGGG$所需的最大跃迁次数最小化。事实证明，这样的星球总是恰好有一个或两个。当有两个这样的星球时，它们总是通过跃迁通道直接相邻，$RGGG$会将自身平均分配到这两个星球上。

你的任务是编写一个程序，找出$RGGG$的最佳星球位置。对于这个问题，戈雷利安人征服的太空区域被定义为一个从$(0,0,0)$到$(1000,1000,1000)$的立方体。

输入

输入包含多组测试数据，每组数据表示戈雷利安人征服一个太空区域的场景。每组场景独立处理。

每组场景的第一行是一个整数$N$，表示戈雷利安人征服的星球总数。接下来的$N$行按照征服顺序指定被征服星球的$ID$和坐标，格式为$ID X Y Z$。$ID$是一个从$1$到$1000$的整数，$X$、$Y$和$Z$是从$0$到$1000$的整数，每个数字之间用一个空格分隔。当$N=0$时，表示输入结束。

输出

对于每个输入场景，输出$RGGG$应重新定位的最佳星球的$ID$。如果只有一个最佳星球，直接输出该星球的$ID$；如果有两个最佳星球，按$ID$从小到大的顺序输出这两个$ID$，中间用一个空格分隔。

输入示例

5
1 0 0 0
2 0 0 1
3 0 0 2
4 0 0 3
5 0 0 4
5
1 0 0 0
2 1 1 0
3 3 2 0
4 2 1 0
5 3 0 0
10
21 71 76 4
97 32 5 69
70 33 19 35
3 79 81 8
31 91 17 67
52 31 48 75
48 90 14 4
41 73 2 21
83 74 41 69
26 32 30 24
0

输出示例

3
2 4
31 97

来源

2006年美国中北部地区