Description

Chuanzhi Advanced Institute has recruited a total of $n$ volunteers to take charge of cleaning activities. Now you need to help count each volunteer’s work status, so that an honor roll can be made and little flowers can be given to them.

The $i$-th volunteer has a working time $t_i$ and a difficulty coefficient $k_i$ for the work they are responsible for. A volunteer’s contribution can be determined by $k_i \times t_i$.

Now you need to sort these volunteers by contribution from high to low. For volunteers with the same contribution, the one with a longer working time should be ranked first. If both contribution and working time are the same, the volunteer with the smaller index should be ranked first.

Input Format

The first line contains one integer $n$, the number of volunteers.

The next $n$ lines each contain two integers $t_i, k_i$ separated by spaces, representing the working time and difficulty coefficient of the $i$-th volunteer.

Output Format

Output one line with $n$ integers. The $i$-th integer is the index of the volunteer ranked $i$-th. Indices start from $1$.

Note that the time limit of this problem is 5 s, and the input/output size is large. Please pay attention to the impact of constant factors on time usage. We will not give extra running time to contestants using Java and Python.

3
1 2
2 3
3 4

3 2 1

Hint

For $40\%$ of the testdata, $1 \leq n \leq 100$.
For an additional $20\%$ of the testdata, $k_i = 1$.
For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq k_i, t_i \leq 1000$.

However, since this contest uses the ACM rules, you must pass $100\%$ of the testdata to get the score for this problem, and the same applies to the following problems.

Translated by ChatGPT 5