Moloco의 Vitcoin 추첨 (어려움)

월말이 되면 Moloco 직원들은 사내 복지 혜택을 걸고 간단한 추첨을 한다.

당신은 Moloco의 소중한 직원이라 추첨권 $n$장을 받았다. 추첨권 $i$의 상금은 $w_i > 0$ Vitcoin이다.

추첨권 $i$에는 동전이 하나씩 짝지어져 있다. 이 동전은 확률 $p_i$로 앞면이 나오고 확률 $1 - p_i$로 뒷면이 나온다 ($0 < p_i < 1$). 모든 동전 던지기는 서로 독립이다.

각 단계에서 아직 고르지 않은 추첨권을 하나 골라 상금을 즉시 받는다. 그다음 그 추첨권과 짝지어진 동전을 던진다. 앞면이 나오면 추첨이 이어져서 다음 추첨권을 고를 수 있고, 추첨권이 떨어질 때까지 이 과정을 반복한다. 뒷면이 나오면 추첨은 그 자리에서 끝나고, 그때까지 모은 Vitcoin을 모두 가진다.

모든 $w_i$와 $p_i$를 알고 있다. 받는 Vitcoin의 기댓값을 최대로 만드는 추첨권 선택 순서를 구하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 1\,000\,000$).

다음 $n$개 줄에는 각각 두 정수 $w_i$와 $q_i$가 주어진다 ($1 \le w_i \le 10\,000$, $0 < q_i < 10\,000$). 확률은 $p_i = q_i / 10000$이다.

추첨권을 고르는 순서를 나타내는 길이 $n$의 순열을 한 줄에 공백으로 구분해 출력한다. 순열의 원소는 $1$ 이상 $n$ 이하의 정수다.

기댓값을 최대로 만드는 순열이 여러 개면 사전순으로 가장 앞서는 것을 출력한다.

순서 $\sigma_1, \sigma_2, \dots, \sigma_n$으로 고를 때 받는 Vitcoin의 기댓값은 $\sum_{k=1}^{n} w_{\sigma_k} \prod_{j < k} p_{\sigma_j}$이다.

첫 번째 예제에서 순서 $(1, 2, 3)$의 기댓값은 $4.55$이고, 기댓값이 가장 큰 순서는 $8.7$을 주는 $(2, 3, 1)$이다. 세 번째 예제에서는 순서 $(2, 3, 1)$과 $(3, 2, 1)$의 기댓값이 같지만 $(2, 3, 1)$이 사전순으로 앞선다.