You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

  通过其它题目的练习，不难发现它们都是以多个测试点，每个测试点给定一定分数来计算最终得分，满分是 100。

  然而我们今年引入的新类型 SPJ 题目与这些题目有些不同，将根据你近似解的精确程度，或者是你程序的运行速度来计算分数。

  因此，这种类型题目的分数上限将不再是 100，理论上你的程序越优秀，所得分数就越高。

Description

  旅行商问题（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

  它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

  所谓NP困难问题，意思是到目前为止还找不到能够在多项式的时间内求解最短回路的算法。

  然而，在现实生活中的旅行商问题，很多情况下我们并不需要求得最精确的最短回路，如果某一个解足够接近事实上的最优解，我们也认为这个解是可以接受的，并把它看做最优解。

  你有最多 4秒 的时间，请注意在时间结束之前输出结果，否则将被认为超时。

  如果你输出的结果是合法的，那么将按照以下公式来计算得分：

  其中 $n$ 为城市个数，$d$ 为你给出结果的回路总长度。

Format

Input

  第一行是一个整数 $n (n \leq 300)$

  接下来 $n$ 行，每行三个正整数，分别表示城市编号、城市 x 坐标、城市 y 坐标。

Output

  输出一行以空格分隔的数字，每个数字代表城市的编号，表示旅行商应该走的城市的方案。

Samples

3
1 1 0
2 2 0
3 3 0

1 2 3 1

Notes

  上述样例的输出，表明给出的路径方案是 1->2->3->1，计算可知总的路程为 4，因此该测试点最终得分是 $50 \times 3^2 / 4 = 112.5$。同时可以验证，这已经是这个输入的最优解。