우주선 경주

매년 열리는 튜닝 우주선 성간 경주에 $N$대의 우주선이 참가한다. 각 우주선 $i$는 순간적으로 최고 속도 $V_i$까지 가속한 뒤 그 속도로 계속 항행하도록 튜닝되어 있다. 과거 성적에 따라 각 우주선은 출발선에서 $X_i$킬로미터 떨어진 위치에서 출발한다.

경주로는 무한히 길다. 우주선들의 속도가 매우 빠르기 때문에 경주로는 처음부터 끝까지 완전히 직선으로 뻗어 있다. 이 직선 경주로에서 우주선들은 서로 간섭하지 않고 아주 쉽게 서로를 앞지를 수 있다.

많은 관중은 경주의 결과가 이미 정해져 있다는 사실을 아직 알아차리지 못한다. 당신이 할 일은, 우주선들이 서로를 몇 번 앞지르는지 알려 주고, 처음으로 일어나는 $10\,000$번의 추월을 시간 순서대로 예측하여 관중에게 보여 주는 것이다.

각 우주선의 출발 위치는 모두 다르다고 가정해도 된다. 또한 어떤 순간에도 경주로 위의 같은 위치에 우주선이 세 대 이상 동시에 있는 일은 결코 없다.

입력은 여러 개의 경주로 이루어진다. 각 경주의 첫 줄에는 참가하는 우주선의 수 $N$ ($0 < N \le 250\,000$)이 주어진다. 이어지는 $N$개의 줄은 각각 한 우주선의 정보를 담는다. $i+1$번째 줄에는 두 정수 $X_i$와 $V_i$가 주어지며, 각각 $i$번째 우주선의 출발 위치와 속도를 나타낸다 ($0 \le X_i \le 1\,000\,000$, $0 < V_i < 100$). 우주선들은 출발 위치 순으로 정렬되어 있다. 즉 $X_1 < X_2 < \cdots < X_N$이다. 출발 위치는 출발선을 지나 우주선이 출발하는 지점까지의 킬로미터 수이고, 속도는 초당 킬로미터 단위로 주어진다.

입력은 우주선이 $0$대인 경주로 끝나며, 그 경주에 대해서는 아무것도 출력하지 않는다.

각 경주마다 다음을 출력한다. 첫 줄에는 경주 동안 우주선들이 서로를 앞지르는 총 횟수를 $1\,000\,000$으로 나눈 나머지를 출력한다.

이어지는 각 줄은 하나의 추월을 시간 순서대로 나타낸다. 추월이 $10\,000$번보다 많으면 처음 $10\,000$번만 출력하고, $10\,000$번보다 적으면 모든 추월을 출력한다. 각 줄은 두 정수 $i$와 $j$로 이루어지며, 이는 우주선 $i$가 우주선 $j$를 앞질렀음을 뜻한다. 여러 추월이 같은 시각에 일어나면, 경주로 위의 위치 순으로 정렬한다. 즉 출발선에 더 가까운 곳에서 일어난 추월을 먼저 출력한다. 추월이 일어난 시각은 두 우주선이 같은 위치에 있게 되는 시각이다.