Racing Champions

In an infinite straight‐line race, there are (n) racing cars labeled (g_1, g_2, \ldots, g_n). Car (g_i) starts at position (k_i) (i.e. its distance from the starting line) and moves at a constant speed (v_i) (units per second). During the race, if a car is ever in the lead (meaning no other car is ahead of it at that moment), it will eventually receive an award. (Note that even if several cars tie for the lead at some moment, they all are considered to have led.)

Your task is to determine which cars will win an award. In other words, for each car, decide if there exists a time (t \ge 0) such that (k_i + v_i,t \ge k_j + v_j,t) for all (1 \le j \le n).

This can be rephrased as: given a set of lines (f_i(t)=k_i+v_i t) (with (t\ge 0)), find those lines that are part of the upper envelope (i.e. they are maximum for some (t \ge 0)).

Input/Output Note: All cars are numbered from 1 to (n) in the order of input. In the output, list the winning car indices in increasing order (separated by a single space).

Hint: One approach is to sort the cars appropriately and compute the upper envelope by finding the intersection times of the linear functions. Beware of cars with identical speeds. For two cars with the same speed, the one with the higher (k) is always ahead (and wins) while the one with lower (k) never takes the lead.

inputFormat

The first line contains a single integer (n) (the number of cars). Each of the next (n) lines contains two space‐separated integers (k_i) and (v_i) (the starting position and constant speed of the (i)th car respectively).

outputFormat

Output a single line containing the indices of the winning cars (i.e. those that are at some moment in the lead) in increasing order, separated by a single space.

sample

3
5 1
0 2
-1 3

1 3