题目描述

题目译自 eJOI2017 Problem B. Particles

两个线性粒子加速器 $A$ 和 $B$ 对向放置，间距为 $L$。它们正在加速基本粒子，$A$ 正在加速 $x$ 粒子，$B$ 正在加速 $y$ 粒子。这两种粒子相对运动，当一个 $x$ 粒子与 $y$ 粒子相遇时，它们相互碰撞并湮灭。需要注意的是，$x$ 粒子可以超越其他 $x$ 粒子，$y$ 粒子可以超越其他 $y$ 粒子，并不对各自超越的粒子产生影响。

像这样，对于给定的一些时间点，从这两个粒子加速器中射出了 $N$ 个 $x$ 粒子和 $N$ 个 $y$ 粒子。每个粒子都以自己恒定的速度做匀速直线运动。粒子按射出顺序编号为 $1$ 到 $N$，对于 $x$ 粒子和 $y$ 粒子均满足以上条件。

注：对于一段时间 $t$，速度为 $v$ 的粒子运动的距离为 $s=vt$。

对于 $x$ 粒子，射出时刻为 $0=t_{x_1}<t_{x_2}<\ldots<t_{x_N}$，它们的速度分别为 $v_{x_1},v_{x_2},\ldots,v_{x_N}$。同样的，对于 $y$ 粒子，射出时刻为 $0=t_{y_1}<t_{y_2}<\ldots<t_{y_N}$，它们的速度分别为 $v_{y_1},v_{y_2},\ldots,v_{y_N}$。

粒子的射出满足如下条件：

• 每个粒子都会和对向粒子碰撞。
• 对于前 $K$ 次碰撞，当两个粒子碰撞时，其他所有粒子距离碰撞点之间的距离均大于或等于 $1$。

写一个程序确定两种粒子之间的前 $K$ 次碰撞。

输入格式

第一行三个整数 $N,L,K$。

接下来 $N$ 行，每行两个非负整数 $t_{x_i},v_{x_i}$，表示第 $i$ 个 $x$ 粒子的射出时刻与速度。

接下来 $N$ 行，每行两个非负整数 $t_{y_i},v_{y_i}$，表示第 $i$ 个 $y$ 粒子的射出时刻与速度。

输出格式

输出 $K$ 行，每行包含两个正整数，第 $i$ 行表示第 $i$ 次碰撞中的 $x$ 粒子与 $y$ 粒子的编号。按碰撞次数递增的顺序输出——从第一次到第 $K$ 次。

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

4 2
2 4

数据范围与提示

对于所有数据，$1\le N\le 50\ 000,1\le L\le 10^9,1\le K\le 100,K\le N$。保证 $0\le t_{x_i},t_{y_i}\le 10^9,1\le v_{x_i},v_{y_i}\le 10^9$。

• 对于 $30\%$ 的数据，$N\le 10^3$。