Lottery for Vitcoins at Moloco (Hard)

Time limit2sMemory limit512 MB

Summary

Order the tickets to maximize the expected sum of prizes, where ticket i stops the lottery with probability 1 - p_i, and break ties by the lexicographically smallest permutation.

Level: Medium7 of 10
Topics: Greedy, Sorting, Math, Probability
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Note

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.

Examples3

Example 1
Input
```
3
2 3000
5 5000
7 2000
```
Expected output
```
2 3 1
```
Example 2
Input
```
3
3 5000
5 1500
7 2000
```
Expected output
```
3 1 2
```
Example 3
Input
```
3
1 4000
1 5000
1 5000
```
Expected output
```
2 3 1
```