레이스

N개의 우주선이 레이스를 한다. i번째 우주선은 시간 0에 즉시 최고 속도 V[i]에 도달하며, 레이스가 끝날 때까지 그 속도를 유지한다. 각 우주선은 이전 대회 결과에 따라 시작점 X[i]에서 출발한다. 레이스장은 무한히 길고 X축과 평행하며, 모든 우주선은 X축과 평행한 방향으로만 움직인다.

레이스 도중 한 우주선이 다른 우주선을 추월할 수 있다. 각 우주선은 X[i]와 별도로 Y, Z 좌표를 가지므로 충돌은 고려하지 않는다.

레이스가 끝날 때까지 일어나는 추월을 구하는 프로그램을 작성하라. 레이스는 더 이상 추월이 일어나지 않을 때 끝난다. 먼저 전체 추월 횟수를 구하고, 시간순으로 처음 10,000개의 추월에 대해 어떤 우주선이 어떤 우주선을 추월하는지 출력해야 한다. 모든 X[i]는 서로 다르며, 임의의 순간에 같은 x좌표에는 최대 두 우주선만 있을 수 있다고 가정한다.

첫째 줄에 우주선의 개수 N이 주어진다. (1 <= N <= 250,000)

다음 N개의 줄에는 i = 1, 2, ..., N의 순서대로 두 정수 X[i], V[i]가 주어진다. 여기서 0 <= X[i] <= 1,000,000, 1 <= V[i] <= 99이며, X[1] < X[2] < ... < X[N]을 만족한다.

첫째 줄에 전체 추월 횟수를 1,000,000으로 나눈 나머지를 출력한다.

그다음 줄부터 각 추월을 시간순으로 출력한다. 전체 추월 횟수가 10,000회를 넘으면 처음 10,000개만 출력한다. 각 줄에는 두 정수 i, j를 출력하며, 이는 i번 우주선이 j번 우주선을 추월한다는 뜻이다. 여러 추월이 동시에 일어나면, 추월이 일어나는 x좌표가 더 작은 것을 먼저 출력한다.