Biathlon

Time limit2sMemory limit512 MB

Summary

Given each competitor's two speeds, find all indexes that can win for some choice of the two track distances.

Level: Medium7 of 10
Topics: Geometry, Sorting, Greedy, Binary search
Solved: No attempts yet

Problem

Piggy is organizing a biathlon race with two disciplines. She invited $N$ competitors, and the race runs under these rules.

Competitor $i$ covers the first discipline at speed $V_1$ and the second discipline at speed $V_2$ .
Each competitor holds that speed over the whole of the matching track.
The distance covered in time $t_1$ in the first discipline is $S_1 = V_1 t_1$ , and the distance covered in time $t_2$ in the second discipline is $S_2 = V_2 t_2$ .
A competitor wins when the sum of his two times is strictly smaller than the sum of the two times of every other competitor.

As the organizer, Piggy picks the two distances $S_1$ and $S_2$ freely among the non-negative real numbers. A competitor is a potential winner when some choice of $S_1$ and $S_2$ makes him win. Find every potential winner.

Input

The first line contains the number of competitors $N$ . ( $1 \le N \le 2 \times 10^5$ )

Each of the next $N$ lines contains the two speeds $V_1$ and $V_2$ of competitor $i$ , separated by a space. ( $1 \le V_1, V_2 \le 10^6$ , $i = 0, 1, \dots, N-1$ )

Output

On one line, print the indexes of the potential winners in increasing order, separated by spaces. Indexing starts from 0. If no competitor can win, print -1 on that line.

Examples5

Example 1
Input
```
4
1 4
2 2
4 1
3 3
```
Expected output
```
0 2 3
```
Example 2
Input
```
3
3 3
3 3
2 2
```
Expected output
```
-1
```
Example 3
Input
```
1
5 7
```
Expected output
```
0
```
Example 4
Input
```
2
5 5
5 5
```
Expected output
```
-1
```
Example 5
Input
```
2
1 2
2 1
```
Expected output
```
0 1
```