无论目的地在哪里,无论我们遇见谁,让我们一起渲染这首歌。
在笛卡尔坐标平面上有一个大小为 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
注意
第一个示例对应图例中的初始设置,下图中舞者的轨迹用不同的颜色标记。
在第二个示例中,没有舞者发生碰撞。