Problem 1560. -- Ceoi2003 Race

1560: Ceoi2003 Race

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 1
[Submit][Status][Web Board]

Description

在一年一次的星际调谐太空船竞赛中,N个太空船参加竞赛;每个太空船i都被如此调谐使得它能在零时间内加速到它的最高速度Vi,并且保持这种巡航速度;由于过去竞赛的成果,每个太空船i开始位置为Xi,
竞赛路线是无限长的,由于太空船高速度,因此每个太空船的竞赛路线是直线的,在这样的直线竞赛路线中,一个太空船是容易超过另一个太空船而且相互不受影响。
大多数观众不能意识到竞赛的结果是可以预先决定的,你的任务就是把结果预先告诉给观众:有多少次一个太空船超过另一个太空船,并预告按时间顺序的最先10000次太空船超过另一个太空船情况。假设每个太空船是在不同位置开始的,并且在竞赛中的任何时刻都不会有多于2个太空船在同一位置。

Input

第1行为整数N(0 < N ≤ 250 000),第i+1行为Xi 和 Vi。其中(0 ≤ Xi ≤ 1 000 000, 0 < Vi < 100)。

Output

第 1行为在竞赛过程中将有太空船超过的次数(当次数大于1000000时,输出对1000000取模后的值),接下来的每行是按超过时间顺序输 出两个i和j,表示第i条太空船超过第j条太空船。如果有多余1000条太空船的超过,则输出按时间顺序的最先10000次超过的太空船;如果没有 10000次的太空船超过,则输出所有的;如果有多个太空船在同一时刻超过,则按位置大小的升序排列。超过时间是指2条太空船在同一位置时的时间。

Sample Input

4
0 2
2 1
3 8
6 3

Sample Output

2
3 4
1 2

HINT

Source

[Submit][Status]