题目描述

在一年一度的调谐宇宙飞船星际竞赛中，$N$ 艘宇宙飞船将参赛。每艘宇宙飞船 $i$ 的调谐方式都是这样的，它可以在零时间内加速到它的最大速度 $V_i$ 并继续以那个速度巡航。由于过去的成就，每艘宇宙飞船都从一个起始位置出发，给定其飞船离起跑线的距离。
赛程无限长。因为宇宙飞船速度很快，比赛的路线一直都是笔直的。在直线赛道上，飞船可以很容易地相互通过，而没有互相干扰。
很多观众还没有意识到，比赛的胜负是可以提前预测的。你的任务是向他们展示这一点，告诉他们宇宙飞船将相互经过多少次，并通过按时间顺序预测宇宙飞船经过的前 $10000$ 次。
您可以假设每艘宇宙飞船都从不同的位置开始。此外，任何时候在赛道的同一位置上永远不会有超过两艘飞船。

输入格式

第一行包含一个整数 $N$ 指定了正在竞争的飞船的数量。接下来的 $N$ 行中的每一行都描述了一艘宇宙飞船的特性。第 $i+1$ 行用两个整数 $X_i$ 和 $V_i$ 描述第 $i$ 艘飞船，表示第 $i$ 艘飞船的起始位置和速度。飞船按照起始位置排序，即 $X_1 < X_2 < \cdots < X_N$。 起始位置是飞船开始的起点线后的公里数，速度以千米每秒为单位。

输出格式

第一行应该包含一个整数为飞船在比赛中相互通过的次数，并对 $1000000$ 取模。接下来的每一行都应该按时间顺序表示一个经过。如果要通过 $10000$ 次以上，只输出前 $10000$ 次。如果小于 $10000$ 次，输出所有的次。每一行应该由两个整数 $i$ 和 $j$ 组成，指定飞船 $i$ 经过飞船 $j$。如果多次相互通过同时发生，它们必须按此次赛道位置排序。这意味着发生在起跑线附近的相互通过必须首先列出。路过的时间是两艘宇宙飞船在同一位置的时间

4
0 2
2 1
3 8
6 3

2
3 4
1 2

提示

数据规模与约定

对于 $100 \%$ 的数据，$0 < N \leq 250 000$，$0 \leq X_i \leq 1 000 000$，$0 < V_i < 100$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2003 的 The Race。
由 @求学的企鹅 翻译整理。