题目描述

题目译自 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}$。

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

1. 每个粒子都会和对向粒子碰撞。
2. 对于前 $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$。