在意识到Zookeeper只是一只鸭子之后,动物们推翻了Zookeeper。他们现在必须通过以下形式的格斗锦标赛来决定新的统治者:
最初,动物 $$$0$$$ 为王,而其他人都在排队,动物 $$$1$$$ 排在队列的前面,动物 $$$n-1$$$ 排在后面。排在队伍前面的动物将向国王发起挑战,力量更大的动物将赢得战斗。胜利者将成为国王,而失败者则排在队列的最后。
连续赢得 $$$3$$$ 次的动物将成为整个动物园的统治者。每只动物的力量取决于他连续获胜的次数。动物$$$i$$$ 具有实力$$$A_i$$$ 连续获胜$$$0$$$,$$$B_i$$$ 连续获胜$$$1$$$,$$$C_i$$$ 连续获胜$$$2$$$。最初,每个人都连续获胜$$$0$$$。
对于所有动物,$$$A_i > B_i$$$ 和 $$$C_i > B_i$$$。此外,$$$A_i$$$、$$$B_i$$$、$$$C_i$$$ 的值是不同的(所有 $$$3n$$$ 值都是成对不同的)。
换句话说,不是国王的动物也有力量$$$A_i$$$。国王的实力通常为 $$$B_i$$$ 或 $$$C_i$$$。例外是在第一回合,第一个国王(动物$$$0$$$)拥有力量$$$A_i$$$。
谁是新的统治者,经过了多少次战斗?或者动物们会永远争斗而没有人成为统治者吗?
输入
第一行包含一个整数 $$$n$$$ ($$$4 \leq n \leq 6000$$$) — 动物的数量。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$3$$$ 整数 $$$A_i$$$、$$$B_i$$$ 和 $$$C_i$$$ ($$$0 \leq A_i, B_i, C_i \leq 10^9$$$)。
保证 $$$A_i > B_i$$$ 和 $$$C_i > B_i$$$,并且 $$$A_i$$$、$$$B_i$$$ 和 $$$C_i$$$ 的所有值都是不同的。
输出
在一行中输出两个整数。第一个是将成为统治者的动物的索引,第二个是在某种动物成为统治者之前经过的战斗次数。
如果动物会无限长时间地战斗,则输出 -1 -1。
示例
输入 #1
4 5 1 2 10 8 11 9 0 3 7 4 6
输出 #1
-1 -1
输入 #2
5 11 7 12 8 6 14 2 1 10 13 0 9 5 3 4
输出 #2
1 7
注意
下面描述了第二个示例的事件顺序。请注意,在战斗$$$1$$$中,国王(动物$$$0$$$)拥有力量$$$A_0$$$。比赛以 $$$7$$$ 比赛结束,动物 $$$1$$$ 赢得 $$$5$$$、$$$6$$$ 和 $$$7$$$ 比赛。