一个大型软件项目编写了许多自动化测试来确保质量。当源代码发生变更时，所有自动化测试会按某种顺序运行，以验证代码变更没有破坏现有的功能。只有当所有自动化测试都通过时，代码变更才会被接受。

运行所有这些自动化测试成本很高，因此一旦出现测试失败，剩余的测试将不再运行。执行每个测试都需要一定的 CPU 时间。当出现测试失败时，运行一系列测试的成本是执行到失败测试（含该测试）为止所消耗的 CPU 时间总和。如果所有测试都通过，则运行该系列测试的成本为 0。

某个自动化测试可能依赖于另一个单一自动化测试的输出。例如，自动化测试 A 可能依赖于自动化测试 B 的输出。在这种情况下，测试 B 必须在测试 A 之前执行。注意，测试 B 和测试 A 之间可以运行其他测试。

基于对历史数据的分析和对代码变更的评估，每个自动化测试都有一个已知的通过概率。任何给定测试通过的概率与其他测试通过的概率相互独立。

给定每个测试的执行 CPU 时间、每个测试的失败概率以及依赖关系，请确定测试的执行顺序，以最小化运行该系列测试的预期成本。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示自动化测试的数量。

接下来的 $n$ 行，每行包含三个值：整数 $c$ ($1 \le c \le 10^6$)，实数 $p$ ($0 < p < 1$)，以及整数 $d$ ($0 \le d \le n$)。其中 $c$ 是运行该自动化测试所需的 CPU 时间，$p$ 是该测试通过的概率，$d$ 是该测试所依赖的测试索引，若该测试没有依赖，则 $d=0$。测试按输入顺序从 $1$ 到 $n$ 编号。

每个概率最多包含六位小数。不存在循环依赖。

输出格式

输出 $n$ 行，每行包含一个整数，给出按顺序运行的测试索引。该顺序必须使运行测试的预期成本最小化，且预期成本需在最优解的 $10^{-6}$ 绝对或相对误差范围内。任何满足此约束的顺序均可被接受。

样例

输入 1

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

输出 1

4
1
2
3