Sort the big products
Given
n pairs of numbers (, ), (, ), …, (, ), you are asked to sort them in increasing order if the value of a pair is considered the number Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next
n lines contain two integers (, ) (0 ≤ ≤ ) (1 ≤ ≤ ).Output
The program should print the initial indices after sorting the pairs.
Examples
Input | Output |
5
0 3
0 4
0 1
0 2
0 5 | 3 4 1 2 5 |
6
1 1
0 2
1 2
2 1
0 1
2 3 | 5 1 2 3 4 6 |
Explanation
- [1](0, 3) = 3 • [2](0, 4) = 4 • [3](0, 1) = 1 • [4](0, 2) = 2 • [5](0, 5) = 5
After sorting → 1 2 3 4 5 ⇒ initial indices will be:
[3] [4] [1] [2] [5].
- [1](1, 1) = 2 • [2](0, 2) = 2 • [3](1, 2) = 4 • [4](2, 1) = 4 • [5](0, 1) = 1 • [6](2, 3) = 12
After sorting → 1 2 2 4 4 12 ⇒ initial indices will be:
[5] [1] [2] [3] [4] [6].
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB