题目描述

Ada 有 $N$ 只蚂蚁，编号为 $1$ 到 $N$。她决定测试 John 的专注力。她取一根长度为 $L$ 厘米的棍子，并将蚂蚁释放到棍子上。

蚂蚁释放的位置由一个整数数组 $P$ 表示，其中蚂蚁 $i$ 被释放的位置为 $P_i$（即距离棍子左端 $P_i$ 厘米）。每只蚂蚁以每秒 $1$ 厘米的恒定速度向左或向右移动。蚂蚁的初始方向由数组 $D$ 表示，其中蚂蚁 $i$ 的方向为 $D_i$：$0$ 表示向左，$1$ 表示向右。当两只蚂蚁相遇时，它们会弹开并反转方向。蚂蚁到达棍子的任一端时就会掉落。

Ada 挑战 John 找出蚂蚁掉落的准确顺序。John 需要你的帮助！

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $L$：蚂蚁的数量和棍子的长度。

接下来的 $N$ 行描述每只蚂蚁的位置和方向。第 $i$ 行包含两个整数 $P_i$ 和 $D_i$：蚂蚁 $i$ 的位置和方向。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: A1 A2 ... AN，其中 $x$ 是测试用例编号（从 $1$ 开始），$A_i$ 是第 $i$ 只掉落的蚂蚁的标签。换句话说，第一个掉落的蚂蚁是标签为 $A_1$ 的蚂蚁，第二个是标签为 $A_2$ 的蚂蚁，以此类推。如果多只蚂蚁同时掉落，则按标签的升序输出。

3
1 5
1 1
2 7
4 1
5 0
4 10
8 0
2 1
6 1
4 0

Case #1: 1
Case #2: 2 1
Case #3: 1 2 3 4

提示

在样例 #1 中，只有一只蚂蚁（标签为 $1$），它是唯一掉落的蚂蚁。它掉落的时间为 $4$ 秒。

在样例 #2 中，两只蚂蚁相向而行，在 $0.5$ 秒时相遇并反转方向。蚂蚁 $2$ 随后在 $3$ 秒时到达棍子右端，而蚂蚁 $1$ 在 $5$ 秒时到达左端。因此，蚂蚁 $2$ 先掉落，然后是蚂蚁 $1$。

在样例 #3 中，蚂蚁 $2$ 和 $4$ 相向而行，在 $1$ 秒时相遇。同样，蚂蚁 $1$ 和 $3$ 也相向而行，在 $1$ 秒时相遇。所有 $4$ 只蚂蚁随后改变方向。

• 蚂蚁 $1$ 和 $2$ 移向棍子的两端，并在 $4$ 秒时掉落。
• 蚂蚁 $3$ 和 $4$ 相向而行，在 $3$ 秒时相遇。它们改变方向后移向两端，并在 $8$ 秒时掉落。

限制条件

$1 \le T \le 100$。

$N < L$。

对于所有 $i$，$D_i \in \{0, 1\}$。

对于所有 $i$，$0 < P_i < L$。

所有 $P_i$ 互不相同。

测试集 1

$1 \le N \le 10$。

$1 \le L \le 100$。

测试集 2

$1 \le N \le 10^3$。

$1 \le L \le 10^9$。

测试集 3

$1 \le L \le 10^9$。

最多 $15$ 个测试用例满足：

$1 \le N \le 10^5$。

其余测试用例满足：

$1 \le N \le 10^3$。

翻译由 DeepSeek V4 Pro 完成