빠른 실패

대형 소프트웨어 프로젝트에는 품질을 확인하기 위한 자동화 테스트가 많이 있다. 소스 코드를 수정하면 기존 기능이 깨지지 않았는지 확인하려고 테스트들을 어떤 순서로든 모두 실행한다. 모든 테스트가 통과해야만 코드 변경이 승인된다.

테스트를 모두 실행하는 데는 비용이 많이 들므로, 테스트가 하나라도 실패하면 나머지 테스트는 실행하지 않는다. 각 테스트는 정해진 CPU 시간이 걸린다. 실패가 발생한 경우의 비용은 실행한 테스트 중 실패한 테스트까지의 CPU 시간 합이다. 모든 테스트가 통과한 경우의 비용은 $0$이다.

테스트는 다른 테스트 하나의 출력에 의존할 수 있다. 예를 들어 테스트 A가 테스트 B의 출력에 의존하면, B를 A보다 먼저 실행해야 한다. 둘 사이에 다른 테스트가 실행될 수도 있다.

각 테스트가 통과할 확률은 과거 데이터 분석과 이번 코드 변경에 대한 평가를 바탕으로 미리 알려져 있다. 한 테스트의 통과 여부는 다른 테스트의 통과 여부와 독립이다. 각 테스트의 CPU 시간, 각 테스트의 실패 확률, 의존 관계가 주어졌을 때, 기대 비용이 최소가 되도록 테스트를 실행할 순서를 정하라.

첫째 줄에 테스트의 개수를 나타내는 정수 $n$ ($1\leq n\leq 10^5$)이 주어진다.

이후 $n$개의 줄에 세 값이 주어진다. 정수 $c$ ($1\leq c\leq 10^6$), 실수 $p$ ($0<p<1$), 정수 $d$ ($0\leq d\leq n$)이다. $c$는 테스트를 실행하는 데 필요한 CPU 시간이고, $p$는 테스트가 통과할 확률이며, $d$는 이 테스트가 의존하는 테스트의 번호이다. 의존하는 테스트가 없으면 $0$이다. 테스트는 입력 순서대로 $1$부터 $n$까지 번호가 매겨져 있다.

각 확률은 소수점 이하 여섯 자리 이하로 주어진다. 순환 의존 관계는 없다.

$n$개의 줄을 출력한다. 각 줄에는 정수 하나를 쓰며, 테스트를 실행할 순서대로 테스트 번호를 적는다. 이 순서의 기대 비용은 최적 기대 비용과 절대 오차 또는 상대 오차가 $10^{-6}$ 이내여야 한다. 이 조건을 만족하는 순서는 모두 정답으로 인정된다.