在瓦坎达王国,2020年的经济危机对各个城市及其周边地区造成了很大的影响。各个城市都制定了在它们之间修建一条高铁的计划,以提振经济,但由于资金不足,每个城市只能与另一个城市建设一条铁路,而且它们想一起建。
计划中配对的城市将分担修建铁路的费用,其中一个城市可能需要比另一个城市支付更多费用。每个城市都知道修建自己通往其他城市的铁路部分的估计成本。一个城市不可能与两个不同城市的铁路建设成本相同。
如果在一个计划中,有两个城市没有连接,但在它们之间建造铁路的成本低于它们当前对建造铁路的成本,那么该计划是不可接受的,合作也不会继续。您的任务是为城市创建合适的计划(城市配对),或者说这样的计划不存在。
输入
第一行包含一个整数 $$$N \;(2 \leq N \leq 10^3)\, $$$ — 城市数量。
接下来的 $$$N$$$ 行包含 $$$N-1$$$ 整数 $$$A_{i,1}, A_{i,2}, ..., A_{i,i-1}, A_{i,i+1}, ..., A_{i,N-1}\; (1 \leq A_{i,j} \leq 10^9)\, $$$ — 其中 $$$A_{i,j}$$$ 表示城市 $$$i$$$ 修建通往城市 $$$j$$$ 的铁路的成本。请注意,每行 $$$A_{i,i}$$$ 被跳过。
输出
输出应包含 $$$N$$$ 整数 $$$O_{1}, O_{2}, ..., O_N$$$,其中 $$$O_i$$$ 表示 $$$i$$$ 应该与哪个城市一起建造铁路,如果无法找到稳定的配对,则为 $$$-1$$$。
示例
输入 #1
4 35 19 20 76 14 75 23 43 78 14 76 98
输出 #1
3 4 1 2
输入 #2
4 2 5 8 7 1 12 4 6 7 8 4 5
输出 #2
-1