The Race

Time limit1sMemory limit128 MB

Summary

Count all overtakes among spaceships with given starting positions and speeds, then list the first 10000 in time order.

Level: Hard8 of 10
Topics: Sorting, Greedy, Implementation, Geometry
Solved: No attempts yet

Problem

During the annual interstellar competition for tuned spaceships, $N$ spaceships compete. Each spaceship $i$ is tuned so that it can accelerate in zero time to its maximum speed $V_i$ and then cruise at that speed forever. Because of past achievements, each spaceship starts at position $X_i$ , i.e. it begins $X_i$ kilometers past the starting line.

The race course is infinitely long. Because the spaceships move so fast, the course runs perfectly straight the whole way. On this straight course, spaceships can pass one another very easily, without interfering with each other.

Many spectators have not yet realized that the outcome of the race can be determined in advance. Your task is to show this: report how many times spaceships pass one another, and predict the first $10\,000$ passings in chronological order.

You may assume that every spaceship starts at a different position. Furthermore, no more than two spaceships are ever at the same position on the course at the same time.

Input

The input consists of several races. The first line of each race contains the number of spaceships $N$ ( $0 < N \le 250\,000$ ). Each of the next $N$ lines describes one spaceship: the $(i+1)$ -th line contains two integers $X_i$ and $V_i$ , the starting position and the velocity of the $i$ -th spaceship ( $0 \le X_i \le 1\,000\,000$ , $0 < V_i < 100$ ). The spaceships are ordered by starting position, i.e. $X_1 < X_2 < \cdots < X_N$ . The starting position is the number of kilometers past the starting line where the spaceship starts, and the velocity is given in kilometers per second.

The input is terminated by a race with $0$ spaceships; no output should be produced for that race.

Output

For each race, output the following. The first line contains the number of times spaceships pass one another during the race, taken modulo $1\,000\,000$ .

Each of the following lines represents one passing, in chronological order. If there are more than $10\,000$ passings, output only the first $10\,000$ ; if there are fewer than $10\,000$ , output all of them. Each line consists of two integers $i$ and $j$ , meaning that spaceship $i$ passes spaceship $j$ . If several passings happen at the same time, sort them by their position on the course: a passing that takes place closer to the starting line is listed first. The time of a passing is the moment when the two spaceships are at the same position.

Examples8

Example 1
Input
```
4
0 2
2 1
3 8
6 3
0
```
Expected output
```
2
3 4
1 2
```
Example 2
Input
```
1
0 5
0
```
Expected output
```
0
```
Example 3
Input
```
3
0 1
1 2
2 3
0
```
Expected output
```
0
```
Example 4
Input
```
3
0 5
1 3
3 1
0
```
Expected output
```
3
1 2
1 3
2 3
```
Example 5
Input
```
4
0 3
2 2
10 3
12 2
0
```
Expected output
```
3
1 2
3 4
1 4
```

Example 6

Input

Expected output

Example 7
Input
```
2
0 5
10 1
0
```
Expected output
```
1
1 2
```
Example 8
Input
```
2
0 1
10 5
0
```
Expected output
```
0
```