P6290 [eJOI 2017] Particles

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.

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

#### 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](www.ejoi.org) Problem C [Particles](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/particles_statement-en.pdf) Translation provided by: @[```_Wallace_```](https://www.luogu.com.cn/user/61430) Translated by ChatGPT 5