← 返回题目列表

Codeforces · 848/B

B. 鲁特之歌

中文机器翻译题面 查看原题

无论目的地在哪里,无论我们遇见谁,让我们一起渲染这首歌。

在笛卡尔坐标平面上有一个大小为 w × h 的矩形舞台,由具有角 (0, 0)、(w, 0)、(w, h) 和 (0, h) 的矩形表示。可见,在上场之前,不会发生碰撞。

舞台两侧站着n位舞者。其中第 i 个属于以下组之一:

- 垂直:站在 (xi, 0) 处,沿 y 正方向(向上)移动;
- 水平:站在 (0, yi) 处,沿正 x 方向(向右)移动。

根据编舞,第 i 个舞者应在前 ti 毫秒内保持静止,然后开始以每毫秒 1 个单位的速度沿指定方向移动,直到到达另一个边界。保证没有两个舞者同时有相同的组别、位置和等待时间。

当两个舞者发生碰撞时(即,当他们都在移动时,在同一点上),他们立即交换移动方向并继续前进。

当到达舞台边界时,舞者停止。找出每个舞者的停止位置。

输入

输入的第一行包含三个空格分隔的正整数 n、w 和 h (1 ≤ n ≤ 100 000, 2 ≤ w, h ≤ 100 000)——分别是舞者的数量以及舞台的宽度和高度。

以下 n 行每行描述一个舞者:其中第 i 行包含三个空格分隔的整数 gi、pi 和 ti (1 ≤ gi ≤ 2, 1 ≤ pi ≤ 99 999, 0 ≤ ti ≤ 100 000),描述一个舞者的组 gi (gi = 1 — 垂直,gi = 2 — 水平)、位置和等待时间。如果 gi = 1,则 pi = xi;否则 pi = yi。保证1≤xi≤w-1和1≤yi≤h-1。保证没有两个舞者同时具有相同的组别、位置和等待时间。

输出

输出 n 行,其中第 i 行包含两个空格分隔的整数 (xi, yi) — 输入中第 i 个舞者的停止位置。

示例

输入 #1

8 10 8
1 1 10
1 4 13
1 7 1
1 8 2
2 2 0
2 5 14
2 6 0
2 6 1

输出 #1

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

输入 #2

3 2 3
1 1 2
2 1 1
1 1 5

输出 #2

1 3
2 1
1 3

注意

第一个示例对应图例中的初始设置,下图中舞者的轨迹用不同的颜色标记。

在第二个示例中,没有舞者发生碰撞。