P6290 [eJOI 2017] 粒子

两台相距 $L$ 的直线粒子加速器相对放置着。加速器 $A$ 发射 $x$ 粒子，加速器 $B$ 发射 $y$ 粒子。这两种粒子相遇时会碰撞并湮灭。注意，一个 $x$ 粒子可以超越另一个 $x$ 粒子，不会发生任何事。对于 $y$ 粒子也是同理。 在这样的条件下，从 $0$ 时刻开始，$A,B$ 加速器 分别开始发射 $N$ 个 $x,y$ 粒子。每一个粒子都以一个固定的速度移动。$x,y$ 粒子分别被编号为 $1,2,\cdots N$。 注：在时间 $t$ 内，速度为 $v$ 的粒子移动的路程为 $s = vt$。 $x$ 粒子的发射时刻从编号 $1$ 到 $N$ 分别为：$0 = tx_1 < tx_2 < tx_3 < \cdots < tx_N$，速度分别为：$vx_1, vx_2, vx_3, \cdots, vx_N$。 相应的， $y$ 粒子的发射时刻分别为：$0 = ty_1 < ty_2 < ty_3 < \cdots < ty_N$，速度分别为：$vy_1, vy_2, vy_3, \cdots, vy_N$。 发射粒子的过程中满足： - 每个粒子会碰撞一个相反类型（$x,y$ 粒子互为相反粒子）的粒子。 - 当两个粒子碰撞时，所有其他粒子到碰撞点的距离将 $\ge 1$。在前 $K$ 次碰撞中，这个条件被满足。 ------------------------ 你的任务是，编写一个程序，确定前 $K$ 次碰撞的粒子对。

第一行，三个正整数，由空格隔开：$N,L,K$。 接下来 $N$ 行，每行两个整数：$tx_i,vx_i$。 再接下来 $N$ 行，每行两个整数：$ty_i,vy_i$。

输出共 $K$ 行。 每行两个正整数 $i,j$，表示第 $i$ 个 $x$ 粒子和第 $j$ 个 $y$ 粒子。 第 $l$ 行表示第 $i$ 个 $x$ 粒子和第 $j$ 个 $y$ 粒子是第 $l$ 个发生碰撞的，即输出顺序代表碰撞的先后顺序。

#### 数据规模与约定 对于所有数据，保证： - $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]$。 其中，对于 $30 \%$ 的数据，有 $1 \le N \le 10^3$。 #### 说明 原题来自：[eJOI2017](www.ejoi.org) Problem C [Particles](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/particles_statement-en.pdf) 翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)