Fail Fast

A large software project has many automated tests to help ensure quality. When a change is made to the source code, the tests run in some sequence to show that the change has not broken existing functionality. The change is accepted if and only if all tests pass.

Running all of these tests is costly, so as soon as one test fails, the remaining tests are not run. Each test takes a fixed amount of CPU time. The cost of a run that hits a failure is the sum of the CPU time of the tests up to and including the failing test. The cost of a run where all tests pass is $0$.

A test may rely on the output of another single test. For example, test A may depend on the output of test B. In that case, test B must run before test A. Other tests may run between them.

Each test has a known probability of passing, based on an analysis of past data and an assessment of the code change. The probability of any test passing is independent of the probability of any other test passing. Given the CPU time to execute each test, the probability of each test's failure, and the dependencies, find an order in which to run the tests that minimizes the expected cost.

The first line contains a single integer $n$ ($1\leq n\leq 10^5$), the number of tests.

Each of the next $n$ lines contains three values: an integer $c$ ($1\leq c\leq 10^6$), a real number $p$ ($0<p<1$), and an integer $d$ ($0\leq d\leq n$). Here $c$ is the CPU time needed to run the test, $p$ is the probability that the test passes, and $d$ is the index of the test it depends on, or $0$ if it has no dependency. Tests are indexed from $1$ to $n$ in the order they are given.

Each probability has at most six decimal digits. There are no cyclic dependencies.

Output $n$ lines, each containing a single integer: the indices of the tests in the order they should run. The expected cost of your order must be within $10^{-6}$ absolute or relative error of the optimal expected cost. Any order that meets this bound is accepted.