You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

两台相距 $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$ 个发生碰撞的，即输出顺序代表碰撞的先后顺序。

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 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 Problem C Particles

翻译提供：@_Wallace_