有一次新年时,迪马做了一个梦,梦中有人向他赠送了一个仙女花环。花环是一组灯,其中一些灯对通过电线连接。迪玛记得花环里的每两盏灯都是通过一些电线直接或间接连接的。而且,电线的数量比灯的数量正好少一根。
这个花环有些不寻常。每个灯都有自己的亮度,亮度取决于灯的温度。温度可以是正值、负值或零。迪马有两个朋友,所以他决定与他们分享花环。他想剪断两根不同的电线,使花环分成三部分。花环的每个部分都应该同样闪亮,即。 e.每个部分的灯温度总和应相等。当然,每个部分都应该是非空的,即。 e.每个部分应至少包含一盏灯。
帮助迪玛找到合适的方法来切割花环,或者确定这是不可能的。
在检查花环时,迪玛拿着一盏灯将其举起。因此,除了他拿着的那盏灯外,每一盏灯现在都挂在一根电线上。因此,您应该打印两个灯 id 作为答案,这表示 Dima 应该切断这些灯所悬挂的电线。当然,迪玛拿着花环的灯不能包含在答案中。
输入
第一行包含单个整数 n (3 ≤ n ≤ 106) — 花环中灯的数量。
接下来是 n 行。其中第 i 个包含有关第 i 个灯的信息:悬挂的灯号 ai(如果没有这样的灯,则为 0)及其温度 ti (- 100 ≤ ti ≤ 100)。灯的编号为 1 到 n。
输出
如果没有解,则打印-1。
否则打印两个整数——灯的索引,这意味着 Dima 应该切断它们悬挂的电线。如果有多个答案,请打印其中任何一个。
示例
输入 #1
6 2 4 0 5 4 2 2 1 1 1 4 2
输出 #1
1 4
输入 #2
6 2 4 0 6 4 2 2 1 1 1 4 2
输出 #2
-1
注意
第一个示例的花环和切割方案: