Spaceship Passing Prediction

In the annual tuned spaceship interstellar competition, N spaceships participate. Each spaceship i starts from a distinct position S_i (its distance from the starting line) and can accelerate instantly to its maximum speed V_i, cruising indefinitely along a straight, infinite track. The spaceships do not interfere with one another when passing. However, a passing event can be predicted beforehand.

A passing event occurs when a spaceship that started behind overtakes one that started ahead. More formally, if spaceship i and spaceship j satisfy \[ S_i V_j, \] then spaceship i will pass spaceship j at time \[ t = \frac{S_j - S_i}{V_i - V_j}. \]

Your task is to compute the total number of passing events and to output the first 10,000 passing events in chronological order. If there are fewer than 10,000 events, output all of them.

Note: It is guaranteed that no three spaceships will be at the same position at the same time (i.e. at any passing moment, only two ships coincide).

inputFormat

The first line contains an integer N (the number of spaceships).

Then follow N lines, each containing two integers S_i and V_i separated by space, representing the starting position and maximum speed of spaceship i respectively. All S_i are distinct.

outputFormat

Output begins with a line containing the total number of passing events.

Then, for the first min(10000, total passing events) events in chronological order, print one line per event with three items: the passing time (in seconds, formatted to 6 decimal places), the index of the spaceship that overtakes, and the index of the spaceship that is passed. The indices refer to the order of input (1-indexed).

sample

2
0 5
10 3

1
5.000000 1 2