Particles
Particles
Two linear particle accelerators A and B, placed opposite to each other at a distance L apart, are propelling elementary particles. A is shooting x-particles, while B is shooting y-particles. The two kinds of particles are flying one opposing the other, and when an x-particle meets a y-particle, they collide and annihilate. One should be aware that an x particle could overtake other x-particles, as well as a y-particle could overtake other y-particles without any consequences for the particles.
Like so, in a given moment of time, which we assume to be zero, a shooting of Nx-particles and Ny-particles starts from the two accelerators. Each particle moves with its own constant speed. The particles are numbered in the order of their shooting from 1 to N, this holds true for both the x-particles and the y-particles.
Remark: For time t, a particle with speed v travels distance s = vt
.
The shooting time moments for the x-particles are 0=tx1
< tx2
< tx3
< ... < txN
, and their speeds are vx1
, vx2
, vx3
, ..., vxN
.
Correspondingly, for the y-particles the moments are denoted by 0=ty1
< ty2
< ty3
< … < tyN
, and their speeds by vy1
, vy2
, vy3
, ..., vyN
.
The shooting is executed in a way to guarantee the fulfillment of the following conditions:
- Each particle will collide a particle of the opposite type;
- When two particles collide, all other particles will be at a distance greater than or equal to 1 from the collision point. This is guarantee for the first К collisions.
Write a program particles to determine the first K collisions between particles of the two kinds.
Input
The three space separated positive integers N (1 ≤ N ≤ 50000),L (1 ≤ L ≤ 109
), and K (1 ≤ K ≤ 100) are read from the first line of the standard input.
The following N lines contain two space separated non-negative integers txi
(0 ≤ txi
≤ 109
) and vxi (1 ≤ vxi
≤ 109
) each: the shooting moment and the speed of the corresponding x-particle.
The last N input lines contain, respectively, each the shooting moment tyi
(0 ≤ tyi
≤ 109
) and the speed vyi (1 ≤ vyi
≤ 109
) of the corresponding y-particle in the same format.
Output
The program must print to the standard output K lines, each containing two space separated positive integers: the numbers of the x-particle and y-particle, which are involved in the corresponding collision.
Lines are output increasingly by the order of collisions – from the first one to the Kth
.
4 100 2 0 1 2 3 3 2 6 10 0 5 3 10 5 1 7 20
4 2 2 4