CF848B.Rooter's Song

Wherever the destination is, whoever we meet, let's render this song together.

On a Cartesian coordinate plane lies a rectangular stage of size w × h, represented by a rectangle with corners (0, 0), (w, 0), (w, h) and (0, h). It can be seen that no collisions will happen before one enters the stage.

On the sides of the stage stand n dancers. The i-th of them falls into one of the following groups:

• Vertical: stands at (x__i, 0), moves in positive y direction (upwards);
• Horizontal: stands at (0, y__i), moves in positive x direction (rightwards).

According to choreography, the i-th dancer should stand still for the first t__i milliseconds, and then start moving in the specified direction at 1 unit per millisecond, until another border is reached. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.

When two dancers collide (i.e. are on the same point at some time when both of them are moving), they immediately exchange their moving directions and go on.

Dancers stop when a border of the stage is reached. Find out every dancer's stopping position.

无论目的地在何方，无论我们遇见谁，让我们共同演绎这首歌曲。

在笛卡尔坐标平面上，有一个尺寸为 $w \times h$ 的矩形舞台，由顶点 $(0, 0)$、$(w, 0)$、$(w, h)$ 和 $(0, h)$ 所构成的矩形表示。可以注意到，在任意舞者进入舞台之前，不会发生任何碰撞。

舞台的各边上共站立着 $n$ 名舞者。其中第 $i$ 名舞者属于以下两类之一：

• 竖直型：站在点 $(x_i, 0)$，沿 $y$ 轴正方向（即向上）移动；
• 水平型：站在点 $(0, y_i)$，沿 $x$ 轴正方向（即向右）移动。

根据编舞要求，第 $i$ 名舞者需在原地静止前 $t_i$ 毫秒，之后以每毫秒 1 单位的速度沿指定方向开始移动，直至抵达舞台另一侧边界为止。保证不存在两名舞者同时属于同一类型、位于同一位置且具有相同的等待时间。

当两名舞者发生碰撞（即在某一时刻，二者均处于运动状态且位于同一点），他们将立即交换各自的运动方向，并继续移动。

舞者一旦抵达舞台边界即停止移动。请确定每名舞者的最终停止位置。

The first line of input contains three space-separated positive integers n, w and h (1 ≤ n ≤ 100 000, 2 ≤ w, h ≤ 100 000) — the number of dancers and the width and height of the stage, respectively.

The following n lines each describes a dancer: the i-th among them contains three space-separated integers g__i, p__i, and t__i (1 ≤ g__i ≤ 2, 1 ≤ p__i ≤ 99 999, 0 ≤ t__i ≤ 100 000), describing a dancer's group g__i (g__i = 1 — vertical, g__i = 2 — horizontal), position, and waiting time. If g__i = 1 then p__i = x__i; otherwise p__i = y__i. It's guaranteed that 1 ≤ x__i ≤ w - 1 and 1 ≤ y__i ≤ h - 1. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.

输入的第一行包含三个用空格分隔的正整数 $n$、$w$ 和 $h$（$1 ≤ n ≤ 100\,000$，$2 ≤ w,\,h ≤ 100\,000$），分别表示舞者的数量以及舞台的宽度和高度。

接下来的 $n$ 行每行描述一名舞者：其中第 $i$ 行包含三个用空格分隔的整数 $g_i$、$p_i$ 和 $t_i$（$1 ≤ g_i ≤ 2$，$1 ≤ p_i ≤ 99\,999$，$0 ≤ t_i ≤ 100\,000$），分别表示该舞者所属的组别 $g_i$（$g_i = 1$ 表示竖直方向，$g_i = 2$ 表示水平方向）、位置和等待时间。若 $g_i = 1$，则 $p_i = x_i$；否则 $p_i = y_i$。保证 $1 ≤ x_i ≤ w - 1$ 且 $1 ≤ y_i ≤ h - 1$。还保证不存在两名舞者具有完全相同的组别、位置和等待时间。

Output n lines, the i-th of which contains two space-separated integers (x__i, y__i) — the stopping position of the i-th dancer in the input.

输出 n 行，其中第 i 行包含两个以空格分隔的整数 (x__i, y__i) —— 表示输入中第 i 个舞者的停止位置。

The first example corresponds to the initial setup in the legend, and the tracks of dancers are marked with different colours in the following figure.

In the second example, no dancers collide.

第一个示例对应图例中的初始设置，舞者的运动轨迹在下图中用不同颜色标出。

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