Nezzar 喜欢 osu! 游戏。
奥苏!在节拍图上播放,节拍图可以看作是由平面上不同点组成的数组。如果对于按顺序列出的任意三个连续点 $$$A,B,C$$$,这三个点之间以 $$$B$$$ 为中心的角度严格小于 $$$90$$$ 度,则称该节拍图为“好”。
左侧的点 $$$A,B,C$$$ 的角度小于 $$$90$$$ 度,因此它们可以是漂亮节拍图的三个连续点;右侧点 $$$A',B',C'$$$ 的角度大于或等于 $$$90$$$ 度,因此它们不能是漂亮节拍图的三个连续点。
现在 Nezzar 拥有 $$$n$$$ 不同点 $$$A_1,A_2,\ldots,A_n$$$ 的谱图。 Nezzar 希望重新排序这些 $$$n$$$ 点,以便生成的节拍图很好。
正式来说,您需要找到从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p_1,p_2,\ldots,p_n$$$,这样beatmap $$$A_{p_1},A_{p_2},\ldots,A_{p_n}$$$ 就不错了。如果不可能,你应该确定它。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5000$$$)。
然后是 $$$n$$$ 行,其中 $$$i$$$- 其中包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — 点 $$$A_i$$$ 的坐标。
保证所有点都是不同的。
输出
如果没有解,则打印$$$-1$$$。
否则,打印 $$$n$$$ 整数,表示有效的排列 $$$p$$$。
如果有多个可能的答案,您可以打印任何一个。
示例
输入 #1
5 0 0 5 0 4 2 2 1 3 0
输出 #1
1 2 5 3 4
注意
这是第一个测试的插图:
请注意,$$$A_1$$$、$$$A_2$$$ 和 $$$A_5$$$ 之间以 $$$A_2$$$ 为中心的角度被视为 $$$0$$$ 度。但是,$$$A_1$$$、$$$A_5$$$ 和 $$$A_2$$$ 之间以 $$$A_5$$$ 为中心的角度被视为 $$$180$$$ 度。