Lottery for Vitcoins at Moloco (Hard)

At the end of each month, Moloco employees take part in a simple lottery for extra employee perks.

As a valuable employee of Moloco, you receive $n$ lottery tickets. Ticket $i$ pays a prize of $w_i > 0$ Vitcoins.

Each ticket $i$ is also paired with a coin. That coin flips heads with probability $p_i$ and tails with probability $1 - p_i$, where $0 < p_i < 1$. Every coin flip is independent.

At each step you choose a ticket among those you have not chosen yet and claim its prize immediately. Then you flip the coin paired with that ticket. On heads the lottery continues and you pick another ticket, and this repeats until you run out of tickets. On tails the lottery ends immediately, and you keep all the Vitcoins you have collected so far.

You know every $w_i$ and every $p_i$. Find an order of picking the tickets that maximizes the expected number of Vitcoins you win.

The first line contains one integer $n$ ($1 \le n \le 1\,000\,000$).

Each of the next $n$ lines contains two integers $w_i$ and $q_i$ ($1 \le w_i \le 10\,000$, $0 < q_i < 10\,000$). The probability is $p_i = q_i / 10000$.

Print, on a single line and separated by spaces, a permutation of length $n$ whose elements are the integers from $1$ to $n$. It describes the order in which you pick the lottery tickets.

If several permutations maximize the expected number of Vitcoins, print the one that comes first lexicographically.

The expected number of Vitcoins for the order $\sigma_1, \sigma_2, \dots, \sigma_n$ is $\sum_{k=1}^{n} w_{\sigma_k} \prod_{j < k} p_{\sigma_j}$.

In the first example the order $(1, 2, 3)$ yields $4.55$, and the maximum is $8.7$, reached by the order $(2, 3, 1)$. In the third example the orders $(2, 3, 1)$ and $(3, 2, 1)$ yield the same expectation, and $(2, 3, 1)$ comes first lexicographically.