Description

Two linear particle accelerators are placed facing each other at a distance of $L$. Accelerator $A$ fires $x$ particles, and accelerator $B$ fires $y$ particles. When these two types of particles meet, they collide and annihilate. Note that an $x$ particle can overtake another $x$ particle and nothing happens. The same applies to $y$ particles.

Under these conditions, starting from time $0$, accelerators $A$ and $B$ begin to fire $N$ $x$ particles and $N$ $y$ particles, respectively. Each particle moves at a constant speed. The $x$ and $y$ particles are numbered $1,2,\cdots,N$.

Note: during time $t$, a particle with speed $v$ travels a distance $s = vt$.

The launch times of the $x$ particles from index $1$ to $N$ are: $0 = tx_1 < tx_2 < tx_3 < \cdots < tx_N$, and their speeds are: $vx_1, vx_2, vx_3, \cdots, vx_N$.

Similarly, the launch times of the $y$ particles are: $0 = ty_1 < ty_2 < ty_3 < \cdots < ty_N$, and their speeds are: $vy_1, vy_2, vy_3, \cdots, vy_N$.

During the firing process, the following conditions hold:

• Each particle will collide with exactly one particle of the opposite type (the $x$ and $y$ particles are opposite types to each other).
• When two particles collide, the distance from every other particle to the collision point will be $\ge 1$. This condition is guaranteed to hold for the first $K$ collisions.

Your task is to write a program to determine the particle pairs in the first $K$ collisions.

Input Format

The first line contains three positive integers separated by spaces: $N, L, K$.

The next $N$ lines each contain two integers: $tx_i, vx_i$.

The next $N$ lines each contain two integers: $ty_i, vy_i$.

Output Format

Output $K$ lines in total.

Each line contains two positive integers $i, j$, indicating the $i$-th $x$ particle and the $j$-th $y$ particle.

Line $l$ means that the $i$-th $x$ particle and the $j$-th $y$ particle are the $l$-th pair to collide, i.e. the output order represents the chronological order of collisions.

4 100 2
0 1
2 3
3 2
6 10
0 5
3 10
5 1
7 20

4 2
2 4

Hint

Constraints

For all testdata, it is guaranteed that:

• $1 \le N \le 5\times 10^4$.
• $1 \le L \le 10^9$.
• $1 \le K \le \min(10^2, N)$.
• $tx_i, ty_i \in [0, 10^9]$.
• $vx_i, vy_i \in (0, 10^9]$.

Among them, for $30\%$ of the testdata, $1 \le N \le 10^3$.

Notes

The original problem is from: eJOI2017 Problem C Particles

Translation provided by: @_Wallace_

Translated by ChatGPT 5