Race

N spaceships are racing. Spaceship i instantly reaches its maximum speed V[i] at time 0 and keeps that speed until the race ends. Each spaceship starts from position X[i], determined by the previous race results. The race track is infinitely long and parallel to the x-axis, and every spaceship moves only in a direction parallel to the x-axis.

During the race, one spaceship may overtake another. Each spaceship also has Y and Z coordinates independent of X[i], so collisions do not need to be considered.

Write a program that finds the overtakes that happen before the race ends. The race ends when no more overtakes can occur. You must first find the total number of overtakes, and then list the first 10,000 overtakes in chronological order, specifying which spaceship overtakes which. Assume all X[i] are distinct, and at any moment at most two spaceships may have the same x-coordinate.

The first line contains the number of spaceships N. (1 <= N <= 250,000)

Each of the next N lines contains two integers X[i] and V[i], for i = 1, 2, ..., N in order. The values satisfy 0 <= X[i] <= 1,000,000 and 1 <= V[i] <= 99, and the starting positions satisfy X[1] < X[2] < ... < X[N].

On the first line, output the total number of overtakes modulo 1,000,000.

On the following lines, output the overtakes in chronological order. If more than 10,000 overtakes occur, output only the first 10,000. Each line must contain two integers i and j, meaning spaceship i overtakes spaceship j. If multiple overtakes happen at the same time, output the one with the smaller x-coordinate first.