描述

在一年一度的星际调校飞船竞赛中，将会有$N$艘飞船参赛。每艘飞船$i$都经过调校，能够在零时间内加速到其最大速度$V_i$，并保持以该速度巡航。由于过往的成绩，每艘飞船都从起始位置$X_i$出发，$X_i$表示飞船距离起跑线的千米数。

赛道无限长。由于飞船的速度很快，赛道始终是笔直的。在这条笔直的赛道上，飞船可以很容易地相互超越，且不会相互干扰。

观众中的许多人尚未意识到，比赛的结果是可以提前确定的。你的任务是向他们展示这一点，方法是告诉他们飞船相互超越的次数，以及按时间顺序预测飞船相互超越的前$10000$次情况。

你可以假设每艘飞船的起始位置都不同。此外，在任何时刻，赛道上的同一位置绝不会出现超过两艘飞船。

输入

输入的第一行指定参赛飞船的数量$N$（$0 < N \leq 250000$）。接下来的$N$行中，每一行描述一艘飞船的属性。第$i + 1$行用两个整数$X_i$和$V_i$描述第$i$艘飞船，分别表示第(i)艘飞船的起始位置和速度$（0 \leq X_i \leq 1000000$，$(0 < V_i < 100)$。飞船是按照起始位置排序的，即$X_1 < X_2 < \cdots < X_N$。起始位置是指飞船出发时距离起跑线的千米数，速度的单位是千米每秒。

输出

输出的第一行应该包含比赛中飞船相互超越的次数对$1000000$取模的结果。通过只公布取模后的超越次数，你既能证明你知道这个次数，又不会让观众中不太聪明的人觉得扫兴。

随后的每一行都应该按照时间顺序表示一次超越情况。如果超越次数超过$10000$次，则只输出前$10000$次超越情况。如果超越次数少于$10000$次，则输出所有的超越情况。每一行应该由两个整数$i$和$j$组成，表示飞船$i$超越了飞船$j$。如果在同一时间发生多次超越，这些超越必须按照它们在赛道上的位置进行排序。这意味着，距离起跑线更近的超越情况必须先列出。一次超越的时间是指两艘飞船处于同一位置的时间。

输入数据 1

4
0 2
2 1
3 8
6 3

输出数据 1

2
3 4
1 2

来源

欧洲信息学奥林匹克竞赛（CEOI）2003 年