Description

In the annual tuning interstellar spaceship race, $N$ spaceships will compete. Each spaceship $i$ is tuned in the following way: it can accelerate to its maximum speed $V_i$ in zero time and then keep cruising at that speed. Due to past achievements, each spaceship starts from a given initial position, specified by its distance from the starting line.
The track is infinitely long. Since spaceships are very fast, the race route is always a straight line. On a straight track, spaceships can pass each other easily without interference.
Many spectators have not realized that the outcome of the race can be predicted in advance. Your task is to show them this by telling how many times the spaceships will pass each other, and by predicting, in chronological order, the first $10000$ passings between spaceships.
You may assume that each spaceship starts at a distinct position. Also, at any time, there will never be more than two spaceships at the same position on the track.

Input Format

The first line contains an integer $N$, specifying the number of spaceships competing. Each of the next $N$ lines describes one spaceship. Line $i+1$ contains two integers $X_i$ and $V_i$, describing spaceship $i$, meaning the initial position and the speed of spaceship $i$. The spaceships are given in increasing order of initial position, i.e. $X_1 < X_2 < \cdots < X_N$. The initial position is the number of kilometers after the starting line where the spaceship starts, and the speed is measured in kilometers per second.

Output Format

The first line should contain an integer: the number of times the spaceships pass each other during the race, taken modulo $10^6$. Each of the following lines should describe one passing in chronological order. If there are more than $10000$ passings, output only the first $10000$. If there are fewer than $10000$, output all of them. Each line should contain two integers $i$ and $j$, indicating that spaceship $i$ passes spaceship $j$. If multiple passings happen at the same time, they must be listed in order of the track position where they occur. This means that passings closer to the starting line must be listed first. The passing time is the time when the two spaceships are at the same position.

4
0 2
2 1
3 8
6 3

2
3 4
1 2

Hint

Constraints

For $100 \%$ of the data, $0 < N \leq 250000$, $0 \leq X_i \leq 10^6$, $0 < V_i < 100$.

Notes

From CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003, The Race.
Translated and organized by @求学的企鹅.

Translated by ChatGPT 5