两个线性粒子加速器 $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=tx_1 < tx_2 < tx_3 < \dots < tx_N$，其速度分别为 $vx_1, vx_2, vx_3, \dots, vx_N$。 相应地，$y$ 粒子的发射时刻为 $0=ty_1 < ty_2 < ty_3 < \dots < ty_N$，其速度分别为 $vy_1, vy_2, vy_3, \dots, vy_N$。

发射过程满足以下条件： - 每个粒子都会与一个异种粒子发生碰撞； - 当两个粒子碰撞时，所有其他粒子距离碰撞点至少为 $1$。这保证了前 $K$ 次碰撞的发生。

任务

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

输入格式

第一行包含三个空格分隔的正整数 $N$、$L$ 和 $K$。 接下来的 $N$ 行，每行包含两个空格分隔的非负整数 $tx_i$ 和 $vx_i$，分别表示对应 $x$ 粒子的发射时刻和速度。 最后 $N$ 行，每行以相同格式分别表示对应 $y$ 粒子的发射时刻 $ty_i$ 和速度 $vy_i$。

输出格式

程序必须向标准输出打印 $K$ 行，每行包含两个空格分隔的正整数：参与相应碰撞的 $x$ 粒子和 $y$ 粒子的编号。 输出行应按碰撞发生的先后顺序排列，从第 $1$ 次到第 $K$ 次。

数据范围

• $1 \le N \le 50\,000$
• $30\%$ 的测试数据中 $N \le 1000$
• $1 \le L \le 10^9$
• $1 \le K \le 100, K \le N$
• $0 \le tx_i, ty_i \le 10^9$
• $1 \le vx_i, vy_i \le 10^9$

样例

输入 1

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

输出 1

4 2
2 4