Particles

Two linear particle accelerators A and B are placed a distance L apart, facing each other. A fires x-particles toward B, and B fires y-particles toward A. When an x-particle and a y-particle flying against each other meet, they collide and annihilate. Particles of the same kind do not affect each other. An x-particle can overtake another x-particle and a y-particle can overtake another y-particle, and nothing happens to either particle when it does.

At time 0 the two accelerators start firing, N x-particles and N y-particles in total. Each particle moves at its own constant speed. The particles are numbered from 1 to N in the order they are fired, separately for the x-particles and the y-particles.

A particle with speed $v$ travels the distance $s = vt$ in time $t$. The firing moments of the x-particles are $0 = t_{x1} < t_{x2} < \dots < t_{xN}$ and their speeds are $v_{x1}, v_{x2}, \dots, v_{xN}$. The firing moments of the y-particles are $0 = t_{y1} < t_{y2} < \dots < t_{yN}$ and their speeds are $v_{y1}, v_{y2}, \dots, v_{yN}$. The firing satisfies the following two conditions.

• Every particle collides with a particle of the opposite kind.
• When two particles collide, every other particle is at distance 1 or more from the collision point. This is guaranteed for the first K collisions.

Write a program that determines the first K collisions between particles of the two kinds.

The first line contains three integers N, L, and K separated by spaces.

Each of the next N lines contains the firing moment $t_{xi}$ and the speed $v_{xi}$ of an x-particle, separated by a space. The $i$-th of these lines describes x-particle $i$.

Each of the last N lines contains the firing moment $t_{yi}$ and the speed $v_{yi}$ of y-particle $i$ in the same format.

Print K lines. Each line contains two integers separated by a space: the number of the x-particle and the number of the y-particle of one collision. Print the collisions in the order they happen, from the first one to the K-th.

• $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$