Particle Accelerator Collision

Two particle accelerators, A and B, are placed facing each other with a distance (L) between them. Accelerator A emits particles of type (x) and accelerator B emits particles of type (y). Each accelerator fires (N) particles. The particles are numbered from (1) to (N) in the order of their emission. The emission times and speeds are given by the sequences ({t^x_i}) and ({v^x_i}) for (x) particles (with (t^x_1 = 0 < t^x_2 < \cdots < t^x_N)) and ({t^y_i}) and ({v^y_i}) for (y) particles (with (t^y_1 = 0 < t^y_2 < \cdots < t^y_N)).

When an (x) particle and a (y) particle meet they collide and annihilate each other. Particles of the same type do not interact even if one overtakes another. It is guaranteed that every particle will eventually annihilate with a particle of the opposite type. Furthermore, for the first (K) collisions, when two particles collide, every other particle is at a distance at least 1 from the collision point.

For an (x) particle with emission time (t^x) and speed (v^x) and a (y) particle with emission time (t^y) and speed (v^y), assuming they have been emitted (i.e. the current time is at least both (t^x) and (t^y)), if they meet at time (t) then their positions satisfy [ v^x(t-t^x)=L-v^y(t-t^y), ] so the collision time is given by [ t=\frac{L+v^x,t^x+v^y,t^y}{v^x+v^y}. ] Since the collision pairing is non-crossing, the eventual pairing is between the (i)th (x) particle and the (i)th (y) particle (for (i=1,2,\ldots,N)). However, the collisions occur in the order determined by the computed collision times. Your task is to determine the pairs of particles involved in the first (K) collisions (ordered in increasing order of collision time). For each collision, output the indices of the (x) and (y) particles that collide.

inputFormat

The first line contains three numbers: (L) (a positive real number), (N) (an integer, the number of particles per accelerator), and (K) (an integer, the number of collisions to report).

The next (N) lines each contain two numbers: (t^x_i) and (v^x_i), representing the emission time and speed of the (i)th (x) particle from accelerator A.

The following (N) lines each contain two numbers: (t^y_i) and (v^y_i), representing the emission time and speed of the (i)th (y) particle from accelerator B.

outputFormat

Output (K) lines. Each line should contain two integers separated by a space: the index of the (x) particle and the index of the (y) particle that collide in that collision, in the order of increasing collision time.

sample

100 2 2
0 1
0.1 100
0 1
0.1 100

2 2
1 1