입자

선형 입자 가속기 A와 B가 거리 L만큼 떨어져 서로 마주 본다. A는 x 입자를 B 쪽으로, B는 y 입자를 A 쪽으로 쏜다. 서로를 향해 날아가던 x 입자와 y 입자가 만나면 두 입자는 충돌해 함께 소멸한다. 같은 종류끼리는 서로 영향을 주지 않는다. x 입자가 다른 x 입자를 앞지르거나 y 입자가 다른 y 입자를 앞지를 수 있고, 앞질러도 두 입자에는 아무 일도 일어나지 않는다.

시각 0에 두 가속기가 발사를 시작해 x 입자 N개와 y 입자 N개를 쏜다. 각 입자는 저마다 일정한 속력으로 움직인다. x 입자와 y 입자 각각에 발사된 순서대로 1번부터 N번까지 번호를 붙인다.

속력이 $v$인 입자는 시간 $t$ 동안 거리 $s = vt$를 움직인다. x 입자의 발사 시각은 $0 = t_{x1} < t_{x2} < \dots < t_{xN}$이고 속력은 $v_{x1}, v_{x2}, \dots, v_{xN}$이다. y 입자의 발사 시각은 $0 = t_{y1} < t_{y2} < \dots < t_{yN}$이고 속력은 $v_{y1}, v_{y2}, \dots, v_{yN}$이다. 발사는 다음 두 조건을 만족하도록 이루어진다.

• 모든 입자는 반대 종류의 입자 하나와 충돌한다.
• 두 입자가 충돌할 때 나머지 입자는 모두 충돌 지점에서 거리 1 이상 떨어져 있다. 이 조건은 처음 K번의 충돌까지 보장된다.

두 종류의 입자 사이에서 일어나는 처음 K번의 충돌을 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 N, L, K가 공백으로 구분되어 주어진다.

다음 N개 줄에는 x 입자의 발사 시각 $t_{xi}$와 속력 $v_{xi}$가 공백으로 구분되어 주어진다. 이 중 $i$번째 줄이 $i$번 x 입자를 나타낸다.

마지막 N개 줄에는 같은 형식으로 y 입자의 발사 시각 $t_{yi}$와 속력 $v_{yi}$가 주어진다.

K개의 줄을 출력한다. 각 줄에는 충돌한 x 입자의 번호와 y 입자의 번호를 공백으로 구분해 출력한다. 첫 번째 충돌부터 K번째 충돌까지 일어난 순서대로 출력한다.

• $1 \le N \le 50000$
• $1 \le L \le 10^9$
• $1 \le K \le 100$, $K \le N$
• $0 \le t_{xi}, t_{yi} \le 10^9$
• $1 \le v_{xi}, v_{yi} \le 10^9$