← 返回题目列表

Codeforces · 1491/I

I. 动物园的统治者

中文机器翻译题面 查看原题

在意识到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$$$ 比赛。