Visible Lines in the Upper Envelope

In an $x-y$ coordinate plane, you are given $n$ lines $L_1, L_2, \dots, L_n$, each defined in the form $y = Ax+B$ (with $|A|,|B| \leq 500000$) and no two lines are identical. When looking downward from $y = +\infty$, if some segment of line $L_i$ is visible (i.e. it appears on the upper envelope of all lines), then $L_i$ is considered visible; otherwise, it is covered. For example, for the lines

• $L_1: y=x$
• $L_2: y=-x$
• $L_3: y=0$

$L_1$ and $L_2$ are visible, while $L_3$ is covered.

Your task is to determine all visible lines. Output the indices of the visible lines (1-indexed) in increasing order. A line is visible if and only if there exists at least one $x$ for which its value is strictly maximum among all given lines.

inputFormat

The first line of input contains an integer $n$ ($1 \leq n \leq 10^5$) representing the number of lines. Each of the following $n$ lines contains two integers $A$ and $B$, representing a line $y = Ax+B$. It is guaranteed that no two lines are identical.

outputFormat

Output a single line containing the indices of all visible lines in increasing order, separated by a space.

sample

3
1 0
-1 0
0 0

1 2